Submission #1334073

#TimeUsernameProblemLanguageResultExecution timeMemory
1334073SpyrosAlivDark Ride (EGOI25_darkride)C++20
16 / 100
1075 ms652 KiB
#include <bits/stdc++.h>
using namespace std;

const int MN = 3e4+5;

int n;
bool isOn[MN];

int ask() {
    cout << "? ";
    for (int i = 1; i <= n; i++) {
        cout << isOn[i];
    }
    cout << endl;
    int ret; cin >> ret;
    return ret;
}

void get_ans(int sz) {
    for (int i = 1; i <= n; i++) {
        isOn[i] = false;
    }
    for (int i = 1; i <= n; i += 2 * sz) {
        for (int j = i; j - i + 1 <= sz; j++) {
            if (j > n) break;
            isOn[j] = true;
        }
    }
    vector<int> a, b;
    for (int i = 1; i <= n; i++) {
        if (isOn[i]) a.push_back(i);
        else b.push_back(i);
    }
    int lo = 0, hi = a.size()-1;
    int idxA = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        for (int i = 0; i <= mid; i++) {
            isOn[a[i]] = false;
        }
        int tot = ask();
        for (int i = 0; i <= mid; i++) {
            isOn[a[i]] = true;
        }
        if (tot % 2 == 0) {
            idxA = mid;
            hi = mid-1;
        }
        else {
            lo = mid+1;
        }
    }
    int idxB = -1;
    lo = 0, hi = b.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        for (int i = 0; i <= mid; i++) {
            isOn[b[i]] = true;
        }
        int tot = ask();
        for (int i = 0; i <= mid; i++) {
            isOn[b[i]] = false;
        }
        if (tot % 2 == 0) {
            idxB = mid;
            hi = mid-1;
        }
        else {
            lo = mid+1;
        }
    }
    cout << "! " << a[idxA] - 1 << " " << b[idxB] - 1 << endl;
}

void solve() {
    cin >> n;
    int fin;
    for (int sz = n/2; sz >= 1; sz /= 2) {
        for (int i = 1; i <= n; i++) {
            isOn[i] = false;
        }
        for (int i = 1; i <= n; i += 2 * sz) {
            for (int j = i; j - i + 1 <= sz; j++) {
                if (j > n) break;
                isOn[j] = true;
            }
        }
        int tot = ask();
        if (tot % 2) {
            fin = sz;
            break;
        }
    }
    get_ans(fin);
}

int main() {
    solve();
    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...