Submission #1361845

#TimeUsernameProblemLanguageResultExecution timeMemory
1361845edoDark Ride (EGOI25_darkride)C++20
100 / 100
1 ms1372 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

map<string, int> memo; // nije ni potreno ali eto

int ask(string s) {
  if (memo.count(s))
    return memo[s];
  cout << "? " << s << endl;
  int res;
  cin >> res;
  return memo[s] = res & 1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  memo[string(n, '0')] = 0;
  memo[string(n, '1')] = 0;
  int D = 0;
  for (int b = 0; b < 15; ++b) {
    string s(n, '0');
    for (int i = 0; i < n; ++i) {
      if (i >> b & 1)
        s[i] = '1';
    }
    if (ask(s))
      D |= (1 << b);
  }

  int h = 31 - __builtin_clz(D);
  int x = 0;
  for (int b = 0; b < 15; ++b) {
    if (b == h)
      continue;
    string s(n, '0');
    for (int i = 0; i < n; ++i) {
      if (!(i >> h & 1) && i >> b & 1)
        s[i] = '1';
    }
    if (ask(s))
      x |= (1 << b);
  }

  cout << "! " << x << " " << (x ^ D) << endl;
  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...