Submission #1355047

#TimeUsernameProblemLanguageResultExecution timeMemory
1355047AMel0nDark Ride (EGOI25_darkride)C++20
100 / 100
2 ms952 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

ll N;
ll DivConq(ll l, ll r, ll bit) {
    // cout << l << ' ' << r << ' ' << bit << endl;
    if (l >= r) return l;
    string s;
    ll cnt = 0;
    ll m = (l + r) / 2;
    for(ll i = 0; i < N; i++) {
        if (i & bit) {
            if (l <= cnt && cnt <= m) s += '1'; 
            else s += '0';
            cnt++;
        }
        else s += '0';
    }
    ll on;
    cout << "? " << s << endl;
    cin >> on;
    if (on % 2) return DivConq(l, m, bit);
    return DivConq(m+1, r, bit);
}

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    vector<signed char> diff(N+1);
    ll one = -1e18;
    for(ll bit = 1; bit < N; bit <<= 1) {
        string s;
        ll cnt = 0;
        for(ll i = 0; i < N; i++) {
            if (i & bit) {s += '1'; cnt++;}
            else s += '0';
        }

        ll on;
        cout << "? " << s << endl;
        cin >> on;
        if (on % 2) {
            diff[bit] = 1;
            if (one == -1e18) {
                ll b = DivConq(0, cnt-1, bit);
                ll cnt2 = 0;
                for(ll i = 0; i < N; i++) {
                    if (i & bit) {
                        if (cnt2 == b) one = i;
                        cnt2++;
                    }
                }
            }
        }
    }
    ll two = one;
    for(ll bit = 1; bit <= N; bit++) if (diff[bit]) two ^= bit;
    cout << "! " << one << ' ' << two << endl;
}
#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...