제출 #1351199

#제출 시각아이디문제언어결과실행 시간메모리
1351199rieyuwDark Ride (EGOI25_darkride)C++20
100 / 100
1 ms468 KiB
#include<bits/stdc++.h>

using namespace std;
#define sz(x) (int)(x).size()
 
const int INF = 1e9 + 7;
//const long long INF = 1e18 + 7;
//const int mod = 998244353; 
const int mod = 1e9 + 7;
//const int inv2 = 499122177;
const int mxN = 1e7;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("_.in", "r", stdin);
    //freopen("_.out", "w", stdout);
    int n; cin >> n;
    string s(n, '0');

    auto query = [&](int x, int y) -> int
    {
        for (int i = 0; i < n; ++i)
            s[i] = '0' + (((i >> x) & 1) || ((i >> y) & 1));
        cout << "? " << s << endl;
        int res; cin >> res;
        return res;
    };
    
    
    int xxor = 0;
    int max_b = 1;
    while((1 << max_b) < n)
        ++max_b;
    //cout << "n: " << n << ", max bits needed: " << max_b << "\n"; 
    int j;
    for (int i = 0; i < max_b; ++i)
    {
        int res = query(i, 29);
        if (res % 2)
        {
            xxor ^= (1 << i);
            j = i;
        }
    }
    //cout << "Found xor as " << xxor << "\n";
    int A = 0, B = 0;
    A ^= (1 << j);
    for (int i = 0; i < max_b; ++i)
    {
        if (i == j) continue;
        int res = query(i, j);
        if ((xxor >> i) & 1)
        {
            if (res % 2)
                A ^= (1 << i);
            else
                B ^= (1 << i);
        }
        else if (res % 2 == 0)
        {
            A ^= (1 << i);
            B ^= (1 << i);
        }
    }
    cout << "! " << A << " " << B << endl;

   
    return 0;
}
#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...