제출 #1363297

#제출 시각아이디문제언어결과실행 시간메모리
1363297biserailievaDark Ride (EGOI25_darkride)C++20
17 / 100
5 ms4912 KiB
#include <bits/stdc++.h>
using namespace std;

int n;

int ask(const vector<int>& ones) {
    string s(n, '0');
    for (int x : ones) s[x] = '1';
    cout << "? " << s << endl;
    int l; cin >> l;
    return l;
}

int find_one(vector<int>& block) {
    int l = 0, r = (int)block.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> ones;
        for (int i = l; i <= mid; i++) ones.push_back(block[i]);
        int x = ask(ones);
        if (x % 2 == 1) r = mid;
        else l = mid + 1;
    }
    return block[l];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<vector<int>> blocks(1);
    blocks[0].resize(n);
    iota(blocks[0].begin(), blocks[0].end(), 0);
    vector<vector<vector<int>>> history; 
    while (true) {
        history.push_back(blocks);
        vector<int> ones;
        for (auto &b : blocks) {
            int mid = b.size() / 2;
            for (int i = 0; i < mid; i++) {
                ones.push_back(b[i]);
            }
        }
        int x = ask(ones);
        vector<vector<int>> new_blocks;
        if (x % 2 == 1) {
            for (auto &b : blocks) {
                int mid = b.size() / 2;
                vector<int> left(b.begin(), b.begin() + mid);
                vector<int> right(b.begin() + mid, b.end());
                if (!left.empty()) new_blocks.push_back(left);
                if (!right.empty()) new_blocks.push_back(right);
            }
        } else {
            for (auto &b : blocks) {
                int mid = b.size() / 2;
                vector<int> left(b.begin(), b.begin() + mid);
                if (!left.empty()) new_blocks.push_back(left);
            }
        }
        blocks = new_blocks;
        for (auto &b : blocks) {
            if (b.size() == 1) {
                int A = b[0];
                vector<int> rest;
                for (int i = 0; i < n; i++) {
                    if (i != A) rest.push_back(i);
                }
                int B = find_one(rest);
                cout << "! " << A << " " << B << endl;
                return 0;
            }
        }
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…