제출 #1363298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363298		biserailieva	Dark Ride (EGOI25_darkride)	C++20	0 / 100	0 ms	436 KiB

Main

#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 main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    vector<int> all(n);
    iota(all.begin(), all.end(), 0);

    vector<vector<int>> queries;
    vector<int> parity;

    vector<int> cur = all;

    while ((int)cur.size() > 1) {
        int mid = cur.size() / 2;
        vector<int> left(cur.begin(), cur.begin() + mid);

        int x = ask(left);

        queries.push_back(left);
        parity.push_back(x % 2);

        cur = left;
    }

    int A = cur[0];

    vector<bool> possible(n, true);
    possible[A] = false;

    for (int i = 0; i < (int)queries.size(); i++) {
        auto &S = queries[i];
        vector<bool> inS(n, false);
        for (int x : S) inS[x] = true;

        for (int j = 0; j < n; j++) {
            if (j == A) continue;

            if (parity[i] == 1) {
                if (inS[A] == inS[j]) possible[j] = false;
            } else {
                if (inS[A] != inS[j]) possible[j] = false;
            }
        }
    }

    int B = -1;
    for (int i = 0; i < n; i++) {
        if (possible[i]) {
            B = i;
            break;
        }
    }

    cout << "! " << A << " " << B << endl;
    return 0;
}

• 서브태스크 1: 0 / 0
• 서브태스크 2: 0 / 9
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 17
• 서브태스크 5: 0 / 16
• 서브태스크 6: 0 / 14
• 서브태스크 7: 0 / 29