Submission #1214637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214637		omarrrr	Zagrade (COI20_zagrade)	C++20	100 / 100	238 ms	1616 KiB

zagrade

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define mpr make_pair

const ll N=2e6 + 10 , mod=1e9 + 7, inf=1e18;

using namespace std;

ll n,m,k,q,c,x,y;
ll t[N];
vector<bool>vis(false,1000);

int main(){
     ios_base::sync_with_stdio (0); cin.tie(0),cout.tie(0);

//    freopen("dining.in","r",stdin);
//    freopen("dining.out","w",stdout);




    ll T=1;
    //cin>>T;
    while(T--){
        cin>>n>>q;
        string ch="";

        ll l=1,r=2,tot=1,y=0;

        priority_queue<ll>pq;
        vector<char>v(n+5,'.');
        v[1]='.';
        pq.push(1);
        while(tot<n){
            cout<<"? "<<l<<" "<<r<<endl;
            cin>>x;
            if(x==1){
                v[r]=')';
                v[l]='(';
                tot++;
                if(!pq.empty()){
                    l=pq.top();
                    pq.pop();
                }else{
                    pq.push(r+1);
                    l=r+1;
                    r++;
                    tot++;
                }
            }else{
                pq.push(l);
                tot++;
                l=r;
            }
          //  cout<<tot<<" "<<pq.size()<<"\n";
            r++;
            y++;
        }
        ll m=pq.size()/2;
      //  cout<<pq.size()<<pq.top();

        for(ll i=0;i<m-1;i++){
            ll j=pq.top();
            v[j]='(';
            pq.pop();
        }
        for(ll i=0;i<m;i++){
            ll j=pq.top();
            v[j]=')';
            pq.pop();
        }
        cout<<"! ";
        for(ll i=1;i<=n;i++){
            cout<<(v[i]!='.' ? v[i]:'(');
        }
        cout<<endl;





    }


    return 0;
}

/*
10 9
 0
 1
 0
 0
 1
 1
 0
 0
 1
 1
 0

)(()()





*/

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