Submission #1152553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152553		zhehan	Zagrade (COI20_zagrade)	C++20	0 / 100	1235 ms	1100 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

int main(){
    int n, q, check;
    string ans;
    vector<ii> paired;
    cin>>n>>q;
    int ptr=1;
    int counter=0;
    while(ptr<n+1){
        if(ptr==n){
            ptr++;
            continue;
        }
        cout<<"? "<<ptr<<' '<<ptr+1<<endl;
        cin>>check;
        if(check==0){
            ans+='(';
            ++ptr;
        }else{
            ans+="()";
            int pos=ptr+1;
            int c=0;
            int pc=1;
            int distback=0;
            while(check==1){
                while(!paired.empty()&&pc<=paired.size()&&ptr-c-1<=paired[paired.size()-pc].first&&ptr-c-1>=paired[paired.size()-pc].first-paired[paired.size()-pc].second){
                    ptr-=paired[paired.size()-pc].second;
                    distback+=paired[paired.size()-pc].second;
                    pc++;
                }
                if(ptr-c<=1||pos+c>=n){
                    break;
                }
                cout<<"? "<<ptr-c-1<<' '<<pos+c+1<<endl;
                cin>>check;
                if(check==0){
                    break;
                }
                c++;
            }
            for(int i=0;i<c;++i){
                ans+=')';
            }
            ptr+=distback;
            paired.push_back(ii(ptr+1+c,2+2*c));
            ptr+=c+2;
        }
    }
    while(ans.length()<n){
        ans+=')';
    }
    cout<<"! "<<ans;
    return 0;
}   

• Subtask 1: 0 / 14
• Subtask 2: 0 / 7
• Subtask 3: 0 / 57
• Subtask 4: 0 / 22