Submission #1345403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345403		Francisco_Martin	Dark Ride (EGOI25_darkride)	C++20	100 / 100	3 ms	952 KiB

Main

//EGOI 2025 Dark Ride
//https://qoj.ac/contest/2343/problem/13166

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

bool query(vll A,ll n){
    string s(n,'0'); ll res;
    for(auto x:A) s[x]='1';
    cout << "? " << s << endl;
    cin >> res; return (res%2==1);
}

int main(){
    ll n, x=0; vll A;
    cin >> n;
    for(int k=0; k<15; k++){
        vll B;
        for(int i=0; i<n; i++) if((i>>k)&1) B.push_back(i);
        if(query(B,n)) x+=(1<<k), A=B;
    }
    ll l=0, r=A.size()-1;
    while(l<r){
        ll m=(l+r)/2; vll B;
        for(int i=0; i<=m; i++) B.push_back(A[i]);
        if(query(B,n)) r=m;
        else l=m+1;
    }
    cout << "! " << A[l] << " " << (A[l]^x) << endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 17 / 17
• Subtask 5: 16 / 16
• Subtask 6: 14 / 14
• Subtask 7: 29 / 29