Submission #334042

#	Time	Username	Problem	Language	Result	Execution time	Memory
334042		limabeans	Zagrade (COI20_zagrade)	C++17	100 / 100	961 ms	1400 KiB

zagrade

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n, q;
char ans[maxn];


int ask(int l, int r) {
    cout<<"? ";
    cout<<l+1<<" "<<r+1<<endl;
    int x;
    cin>>x;
    return x;
}



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

    cin>>n>>q;


    vector<int> stk;
    for (int i=0; i<n; i++) {
	if (stk.empty()) {
	    stk.push_back(i);
	    continue;
	}
	int res = ask(stk.back(), i);
	if (res==1) {
	    ans[stk.back()]='(';
	    ans[i]=')';
	    stk.pop_back();
	} else {
	    stk.push_back(i);
	}
    }

    int len = stk.size();
    assert(len%2==0);
    for (int i=0; i<len; i++) {
	if (i<len/2) {
	    ans[stk[i]]=')';
	} else {
	    ans[stk[i]]='(';
	}
    }

    cout<<"! ";
    for (int i=0; i<n; i++) {
	cout<<ans[i];
    }
    cout<<endl;
    
    
    return 0;
}

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