[BOJ] Jagged Skyline - Compy's Blog

Jagged Skyline

TimeLimit	MemoryLimit	Condition	TAG
4s	1024MB	(1 ≤ w ≤ 10000, 1 ≤ h ≤ 10^18)	Random(?), Binary Search

와.. 이거는 접근은 잘 됐는데.. 이분탐색에서 if문 조건을 착각해서 시간을 날린 문제.. 헉

접근까지는 그렇게 오래 안 걸리고 뭔가 어느정도 몇개 랜덤으로 보다보면 큰게 나와서 아래거를 좀 제거할 수 있을거 같은데? 이러한 아이디어에서 출발했습니다. 근데 나중에 if문 조건을 잘못 적어버려서 혼났네요.. ㅏ아아아ㅏ아아아아앙 분노의 연속 10번 제출을 해버려서 ㅠㅜ

하튼 재밌었습니다.

endl 쓰는거는 cout flush 해줘야해서 써준 겁니당. 그리고 인터렉트 이거 처음 풀어봤는데 재밌네요!

정답 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <random>
using namespace std;
using ll = long long;
ll w, h;
ll max_height = 0;
ll result_pos = 1;
ll global_cnt;
bool visited[10001];
bool check(ll w, ll h){
    cout << "? " << w << " " << h << endl;
    string response;
    cin >> response;
    return response == "sky";
}

void solution(ll pos){
    global_cnt++;
    if(check(pos, max_height+1)) return;
    
    ll low = max_height;
    ll top = h;
    
    
    while(low < top){
        ll pivot = (low+top) / 2;
        global_cnt++;
        
        if(check(pos, pivot+1)) top = pivot;
        else low = pivot + 1;
    }
    
    if(top > max_height){
        max_height = top;
        result_pos = pos;
    }
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    
    global_cnt = 0;
    cin >> w >> h;
    random_device rd;
    mt19937 gen(rd());
    
    uniform_int_distribution<int> rand_(1, (int)w);
    
    for(int i = 0; i < w; i++){
        int width = rand_(gen);
        while(visited[width]) width = rand_(gen);
        
        visited[width] = true;
        if(global_cnt >= 12000) break;
        solution(width);
        
        if(max_height == h) break;
    }
    
    cout << "! " << result_pos << " " << max_height;
    
    return 0;
}