Submission #318492

#	Time	Username	Problem	Language	Result	Execution time	Memory
318492		kshitij_sodani	Zagrade (COI20_zagrade)	C++14	100 / 100	1094 ms	1324 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
//int aa[1001][1001];
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ord tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
bool ask(int cc,int dd){
/*	if(aa[cc][dd]>-1){
		return aa[cc][dd];
	}*/
	cout<<"? "<<cc+1<<" "<<dd+1<<endl;
	int x;
	cin>>x;
//	aa[cc][dd]=x;

	return x;
}
int ans[100001];
/*void solve(int l,int r){
	for(int i=l+1;i<=r;i+=2){
		if(ask(ind,i)){
			ans[i]=1;
			if(i>l+1){
				solve(l+1,i-1);
			}
			if(i<r-1){
				solve(i+1,r-1);
			}
			break;
		}
	}
}*/
int vis[1001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,q;
	cin>>n>>q;
/*	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			aa[i][j]=-1;
		}
	}*/


	int cur=0;
	vector<int> ss;

	for(int i=0;i<n;i++){
		if(cur==0){
			cur+=1;
			ss.pb(i);
		}
		else{
			int x=ask(ss.back(),i);
			if(x){
				ans[i]=1;
				ss.pop_back();
				cur-=1;
			}
			else{
				cur+=1;
				ss.pb(i);
			}
		}
	}
	for(int j=0;j<ss.size()/2;j++){
		ans[ss[j]]=1;
	}
	cout<<"! ";
	
	for(int i=0;i<n;i++){
		if(ans[i]==0){
			cout<<'(';
		}
		else{
			cout<<")";
		}
	}

	cout<<endl;
	return 0;


/*
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j+=2){
			aa[i][j]=ask(i,j);
		}
	}

	while(true){
		vector<int> ss;
		for(int j=0;j<n;j++){
			if(vis[j]==0){
				ss.pb(j);
			}
		}
		if(ss.size()==0){
			break;
		}
		int st=0;
		for(int i=0;i+1<ss.size();i++){
			if(aa[ss[i]][ss[i+1]]){
				ans[ss[i+1]]=1;
				vis[ss[i]]=1;
				vis[ss[i+1]]=1;
				st=1;
				break;
			}
		}
		if(st){
			continue;
		}

		for(int i=0;i<ss.size()/2;i++){
			ans[ss[i]]=1;
		}
		break;


	}






//	solve(0,n-1);
	cout<<"! ";
	
	for(int i=0;i<n;i++){
		if(ans[i]==0){
			cout<<'(';
		}
		else{
			cout<<")";
		}
	}

	cout<<endl;
*/



	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int j=0;j<ss.size()/2;j++){
      |              ~^~~~~~~~~~~~

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