| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 197 | 32 | 24 | 15.385% |
The king of Belle Aire People's Country has come up with a new plan: he has heard about the popular phenomenon called "King of the Hill", and he would like to become one as well. To do so, he has ordered you to raise a flag on the highest hill in his square kingdom, which has dimensions $n \times n$. You are given a very expensive (it is gold- and jewel-embedded) satellite-based height-measuring system. This equipment is highly accurate: the heights on every location in the kingdom are represented with distinct integers. However, to cut costs, you are only allowed to take 10ドルn+100$ measurements before reporting back to the king.
Furthermore, you know for certain that there is only a single point that is the absolute highest: this is the only point for which its height is larger than the (up to) four orthogonally adjacent points that lie inside the kingdom. In other words, there are no local maxima besides the global maximum.
This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
The interactor first sends one line with an integer $n$ (1ドル\leq n\leq 10,000円$), the width and height of the kingdom.
Then, your program should make at most 10ドルn+100$ queries to find the highest point in the kingdom. Each query is made by printing one line of the form "? $x$ $y$" (1ドル\leq x,y\leq n$). The interactor will respond with an integer $v$ (1ドル \leq v \leq 10^9$), indicating the height at coordinate $(x, y)$.
When you have determined the height of the highest point in the kingdom $v,ドル print one line of the form "!$v$", after which the interaction will stop. Printing the answer does not count as a query.
The interactor is not adaptive: the heights in the kingdom are fixed up front, and do not depend on your queries.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your solution.
Using more than 10ドルn+100$ queries will result in a wrong answer.
3 3 9 4 8 7
? 2 1 ? 2 2 ? 2 3 ? 3 2 ? 1 2 ! 9
4 600000000 864213579 864297531 987654321 123456789 975318642
? 3 3 ? 2 3 ? 2 2 ? 1 2 ? 1 1 ? 1 3 ! 987654321
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2023 K번