백준 26001 (C++) Jagged Skyline

최초 업로드: 2025-09-21 09:19:01

최근 수정 시간: 2025-09-21 09:19:01

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] Jagged Skyline

[문제 링크](https://www.acmicpc.net/problem/26001)

## 문제 설명

The future is here! The Boxes And Parcels Centre has decided to start delivering parcels using drones. Being a BrAinPort Company, naturally the first deliveries will be to Eindhoven.

To keep the flight logic simple, the first prototype will only deliver to the roofs of the tallest buildings. After take-off, the drone will take a $w\times h$ ($1 \leq w\leq 10\,000$, $1\leq h\leq 10^{18}$) photo of the skyline, as shown in Figure J.1. You have been tasked with the problem of determining the location and height of the tallest building in this photo, so that the drone knows where to go.

You have access to a classifier that can determine for each pixel whether it is "<code>sky</code>" or "<code>building</code>". You can use this multiple times for different pixels. To avoid unnecessary delays, you may run the classifier at most $12\,000$ times.

It is guaranteed that the buildings will not contain any hovering parts: whenever a pixel that is not on the bottom row of the photo is classified as building, the pixels below it will also be classified as building.

Figure J.1: The skyline of the sample interaction.

## 인터랙션
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 two integers $w$ and $h$ ($1\leq w\leq 10\,000$, $1\leq h\leq 10^{18}$), the width and height of the photo in pixels.

Then, your program should make at most $12\,000$ queries to find the highest building. Each query is made by printing one line of the form &quot;<code>?</code> $x$ $y$&quot; ($1\leq x\leq w$, $1\leq y\leq h$). The interactor will respond with either &quot;<code>sky</code>&quot; or &quot;<code>building</code>&quot;, indicating the classification of the pixel at coordinates $(x, y)$.

When you have determined the $x$-coordinate of one of the highest buildings and its height $y$, print one line of the form &quot;<code>!</code> $x$ $y$&quot;, after which the interaction will stop. Printing the answer does not count as a query.

The interactor is not adaptive: the skyline is fixed up front, and does not depend on your queries.

If there are multiple valid solutions, you may output any one of them.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Using more than $12\,000$ queries will result in a wrong answer.

## 풀이
최대 12'000번까지 질문할 수 있지만 그냥 linear 하게 보면 $log_210^{18} * 10000$이기에 불가능하다. 여기서 자기보다 낮은 위치는 확인 할 필요가 없기에, y가 증가하는 경로로 살펴보면 된다. 이렇게 구현하더라도 w가 1 증가함에 따라 y도 1씩 증가하는 계단 형태를 띄는 최악의 경우를 피하기 위해 보는 w 순서를 랜덤으로 셔플 해주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll w, h; cin >> w >> h;

vector<int> v(w);
 for(int i=0;i<w;i++) v[i]=i+1;
 shuffle(v.begin(), v.end(), mt19937(chrono::steady_clock::now().time_since_epoch().count()));

ll ans=0, ans_x=1;
 for(int i=0;i<w && ans<h;i++) {
 cout << "? " << v[i] << ' ' << ans+1 << '\n' << flush;
 string input; cin >> input;
 if(input[0]=='s') continue;

ll left = ans+1, right = h;
 while(left<right) {
 ll mid = (left+right+1)/2;
 cout << "? " << v[i] << ' ' << mid << '\n' << flush;
 cin >> input;
 if(input[0]=='b') left=mid;
 else right=mid-1;
 }
 ans = left;
 ans_x = v[i];
 }
 cout << "! " << ans_x << ' ' << ans << '\n' << flush;
}
```