CSacademy) Second Minimum

https://csacademy.com/contest/archive/task/second-minimum/

반씩 나눠가며 각각의 l, r 에 대해  작은 값을 가지고 있다면 한번 분할정복 돌리면 가장작은 값은 바로 나오며

그다음에 토너먼트의 승패표가 있을 때 2등의 후보는 lgN개로 정해져있는 성질이 있기 때문에 다시 순회하면서

lgN개에 대해서만 반복문 한번 돌리면서 가장 작은놈을 구해주면 된다.

2등의 후보는 결승에서 1등한테 진놈, 준결승에서 1등한테 진놈, 준준결승에서 1등한테 진놈, ..... ,1라운드에서 1등한테

진놈이 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
int t[1<<15];
int bigger(int a, int b){
    cout << "Q " << a << " " << b << endl;
    int ret;
    cin >> ret;
    return ret == a;
}
int init(int l, int r, int d){
   if(l==r) return t[d] = l;
   int m = (l+r)>>1;
   int L = init(l, m, 2*d);
   int R = init(m+1, r, 2*d+1);
   return t[d] = bigger(L, R) ? L : R;
}
vector<int> v;
void go(int l, int r, int d){
   if(l==r) return; 
   if(t[d] == t[2*d]) v.push_back(t[2*d+1]);
   else v.push_back(t[2*d]);
   
   int m = (l+r)>>1;
   if(t[d] == t[2*d]) go(l, m, 2*d);
   else go(m+1, r, 2*d+1);
}
int main() {
    cin >> N;
    init(1, N, 1);
    go(1, N, 1);
    int ans = v[0];
    for(int i = 1 ; i < v.size(); i++){
        if(bigger(v[i], ans)) ans = v[i];
    }
    cout << "A " << ans << endl;
    return 0;
}