Submission #1361798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361798		imchy	Dark Ride (EGOI25_darkride)	C++20	24 / 100	4 ms	448 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector<char> s;
pair<int, int> ans={-1,-1};
int n;

int uPrvoj(int l, int r){
    if(l==r){
        return l;
    }
    int pl=l, pr=(r+l)/2;

    for(int i=pl;i<=pr;i++){
        s[i]='1';
    }

    cout<<"?";

    for(int i=0;i<n;i++){
        cout<<s[i];
    }
    cout<<endl;

    int k;
    cin>>k;

    for(int i=pl;i<=pr;i++){
        s[i]='0';
    }

    if(k%2==0)
        return uPrvoj(pr+1, r);

    return uPrvoj(pl, pr);
}

int main(){
    cin>>n;
    s.resize(n);
    for(int i=0;i<n;i++){
        s[i]='0';
    }

    if(n<=30){
    for(int i=0;i<n;i++){
        s[i]='1';
        cout<<"?";
        for(int j=0;j<n;j++)
            cout<<s[j];

        int k;
        cout<<endl;
        cin>>k;
        if(k==1){
            if(ans.first==-1)
                ans.first=i;
            else
                ans.second=i;
        }
        s[i]='0';

        if(ans.first!=-1 && ans.second!=-1){
            cout<<"!"<<ans.first<<" "<<ans.second<<endl;
            return 0;
        }
    }
    }

    else{
        int l=0, r=n-1;
        int a=-1;

        pair<int, int> a1, a2;

        while(a==-1){
            int tr=r;
            r=(r+l)/2;
            for(int i=l;i<=r;i++){
                s[i]='1';
            }

            cout<<"?";
            for(int i=0;i<n;i++){
                cout<<s[i];
            }
            cout<<endl;

            int k;
            cin>>k;

            for(int i=l;i<=r;i++){
                s[i]='0';
            }

            if(k==(r-l+1)*2){
                l=r+1;
                r=tr;
            }
            else if(k==(r-l)*2+1){
                a1.first=l;
                a1.second=r;
                a2.first=r+1;
                a2.second=tr;
                a=1;
            }
        }

        ans.first=uPrvoj(a1.first, a1.second);
        ans.second=uPrvoj(a2.first, a2.second);

        cout<<"!"<<ans.first<<" "<<ans.second<<endl;
    }

    return 0;
}

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