fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int ask(int l,int r){
  5.     cout << "AK " << l << " " << r << "\n" << flush;
  6.     string s;
  7.     if(!(cin >> s)) exit(0);
  8.     if(s=="O") return 1;
  9.     return 0;
  10. }
  11.  
  12. vector<int> solve_interval(int l,int r,int k){
  13.     if(k==0) return {};
  14.     if(l==r){
  15.         int res = ask(l,l);
  16.         if(res==1) return {l};
  17.         else return {};
  18.     }
  19.     int mid = (l+r)/2;
  20.     int res = ask(l,mid);
  21.     if(k==1){
  22.         if(res==1){
  23.             vector<int> a = solve_interval(l,mid,1);
  24.             vector<int> b = solve_interval(mid+1,r,0);
  25.             a.insert(a.end(), b.begin(), b.end());
  26.             return a;
  27.         } else {
  28.             vector<int> a = solve_interval(l,mid,0);
  29.             vector<int> b = solve_interval(mid+1,r,1);
  30.             a.insert(a.end(), b.begin(), b.end());
  31.             return a;
  32.         }
  33.     } else { // k == 2
  34.         if(res==1){
  35.             vector<int> left = solve_interval(l,mid,1);
  36.             vector<int> right = solve_interval(mid+1,r,1);
  37.             left.insert(left.end(), right.begin(), right.end());
  38.             return left;
  39.         } else {
  40.             vector<int> left = solve_interval(l,mid,2);
  41.             if((int)left.size()==2) return left;
  42.             if((int)left.size()==1){
  43.                 // 이 경우 이론상 발생하지 않음. 안전하게 처리: 나머지를 오른쪽에서 찾기
  44.                 vector<int> right = solve_interval(mid+1,r,1);
  45.                 left.insert(left.end(), right.begin(), right.end());
  46.                 return left;
  47.             }
  48.             // left.size() == 0 이면 둘 다 오른쪽에 있음
  49.             vector<int> right = solve_interval(mid+1,r,2);
  50.             return right;
  51.         }
  52.     }
  53. }
  54.  
  55. int main(){
  56.     ios::sync_with_stdio(false);
  57.     cin.tie(nullptr);
  58.     int T;
  59.     if(!(cin >> T)) return 0;
  60.     while(T--){
  61.         int N;
  62.         if(!(cin >> N)) return 0;
  63.         vector<int> ans = solve_interval(1,N,2);
  64.         if((int)ans.size()!=2){
  65.             // 예외 처리: 만약 하나만 찾혔거나 못 찾혔으면, 남은 위치를 브루트로 확인
  66.             set<int> found(ans.begin(), ans.end());
  67.             for(int i=1;i<=N && (int)found.size()<2;i++){
  68.                 if(found.count(i)) continue;
  69.                 int r = ask(i,i);
  70.                 if(r==1) found.insert(i);
  71.             }
  72.             ans.assign(found.begin(), found.end());
  73.         }
  74.         cout << "! " << ans[0] << " " << ans[1] << "\n" << flush;
  75.     }
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
1
10

X

O

X

X

O

X
stdout
copy 
AK 1 5
AK 1 3
AK 1 2
AK 3 3
AK 4 4
AK 4 4
AK 6 8
https://ideone.com/hbhUdf
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!