[BOJ 20929] 중간

https://www.acmicpc.net/problem/20929

20929번: 중간

Tag : binary search

 

문제요약

정렬된 배열 a, b를 합쳤을 때 k번째 수를 2logn번 이하의 쿼리로 구해라.

 

풀이

https://kim1109123.tistory.com/48

위 문제의 시간복잡도가 \(O(logn)\)으로 강제된 문제다. 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, k;
int cnt = 0;

int get(char c, int idx) {
    cnt++;
    assert(cnt <= 40);
    cout << "? " << c << " " << idx << endl << flush;
    int t; cin >> t;
    return t;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n; k = n;
    int lo = 0, hi = n;
    map<int, int> a, b;
    while(lo + 1 < hi){
        int m = (lo + hi) / 2, j = k - m;
        if(m >= k) {
            hi = m;
            continue;
        }
        int am = get('A', m); a[m] = am;
        if(j<=0){lo=m;continue;}
        int bj = get('B', j); b[j] = bj;
        if((1<=j and j<=n and bj<=am) or j<=0)hi=m;
        else lo=m;
    }
    if(a[hi] == 0) a[hi] = get('A', hi);
    int bj = 0; int j = n - hi;
    if(j > 0) bj = get('B', j);
    if((j == 0 or bj <= a[hi]) and (j + 1 > n)) {
        cout << "! " << a[hi] << endl << flush;
        return 0;
    }
    if((j == 0 or bj <= a[hi]) and j + 1 <= n) {
        bj = get('B', j + 1);
        if(bj > a[hi]) cout << "! " << a[hi] << endl << flush;
        else  cout << "! " << bj << endl << flush;
        return 0;
    }
    bj = get('B', j + 1);
    cout << "! " << bj << endl << flush;
}