Submission #312755

#	Time	Username	Problem	Language	Result	Execution time	Memory
312755		AmineTrabelsi	Zagrade (COI20_zagrade)	C++14	100 / 100	973 ms	1200 KiB

zagrade

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) ((int)x.size())
const ll maxint=2e18;
const ll minint =-2e18;

// Hi
bool ask(int i,int j){
	bool response;
	cout << "? "<<i+1<<" "<<j+1<< endl;
    cin >> response;
    return response;
}
int main(){
	sync
	int n, q;
    cin >> n >> q;
    vector<int> st;
    vector<char> res(n,'-');
    for(int i=0;i<n;i++){
    	if(st.empty()){
    		st.pb(i);
    		continue;
    	}
    	int last = st.back();
    	bool r = ask(last,i);
    	if(r){
    		st.pop_back();
    		res[last]= '(';
    		res[i]=')';
    	}else{
    		st.pb(i);
    	}
    }
    if(!st.empty()){
    	int x = sz(st);
    	int to = x/2;
    	if(x&1)to--;
    	while(!st.empty() && to){
    		res[st.back()] = '(';
    		st.pop_back();
    		to--;
    	}
    	while(!st.empty()){
    		res[st.back()] = ')';
    		st.pop_back();
    	}
    }
    cout<<"! ";
    for(auto i:res)cout<<i;
    	cout<<endl;
    
	return 0;
}
/*
3
())
*/

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