Submission #1343853

#TimeUsernameProblemLanguageResultExecution timeMemory
1343853SmuggingSpunDark Ride (EGOI25_darkride)C++20
100 / 100
2 ms584 KiB
#include<bits/stdc++.h>
using namespace std;
int ask(string s){
  cout << "? " << s << endl;
  int x;
  cin >> x;
  return x;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, A = 0, B = 0;
  cin >> n;
  vector<bool>same;
  for(int bit = 0; (1 << bit) < n; bit++){
    string s(n, '0');
    for(int i = 0; i < n; i++){
      if(i >> bit & 1){
        s[i] = '1';
      }
    }
    same.push_back(~ask(s) & 1);
  }
  int LG = same.size();
  vector<int>p;
  for(int bit = 0; bit < LG; bit++){
    if(!same[bit]){
      for(int i = 0; i < n; i++){
        if(i >> bit & 1){
          p.push_back(i);
        }
      }
      break;
    }
  }
  for(int bit = LG - 1; bit > -1; bit--){
    int nA = A | (1 << bit);
    if(nA < p.size()){
      string s(n, '0');
      for(int i = 0; i < nA; i++){
        s[p[i]] = '1';
      }
      if(~ask(s) & 1){
        A = nA;
      }
    }
  }
  A = p[A];
  for(int bit = 0; bit < LG; bit++){
    if(same[bit] == (A >> bit & 1)){
      B |= 1 << bit;
    }
  }
  cout << "! " << A << " " << B;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...