oj.uz

Submission #318415

# Submission time Handle Problem Language Result Execution time Memory
318415 2020-11-01T18:44:42 Z kshitij_sodani Zagrade (COI20_zagrade) C++14
0 / 100
 1629 ms 2704 KB 
#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'
bool ask(int aa,int bb){
	cout<<"? "<<aa+1<<" "<<bb+1<<endl;
	int x;
	cin>>x;
	return x;
}
int ans[100001];
int aa[1001][1001];
/*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 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=i+1;j<n;j+=2){
			aa[i][j]=ask(i,j);
		}
	}

	set<int> ind;
	for(int i=0;i<n;i++){
		ind.insert(i);
	}

	while(ind.size()){
		vector<int> ss;
		for(auto j:ind){
			ss.pb(j);
		}
		int st=0;
	/*	if(ss.size()%2>0){
			while(true){
				continue;
			}
		}*/
		for(int i=0;i<(int)(ss.size())-1;i++){
			if(aa[ss[i]][ss[i+1]]){
				ans[ss[i+1]]=1;
				ind.erase(ss[i]);
				ind.erase(ss[i+1]);
				st=1;
				break;
			}
		}
		if(st){
			continue;
		}
		for(auto j:ss){
			ans[j]=1;
		}
		//cout<<ss.size()<<endl;
		for(int i=(int)(ss.size())/2;i<ss.size();i++){
			ans[ss[i]]=0;
		}
		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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 1629 ms 2676 KB Execution killed with signal 13 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Runtime error 1604 ms 2704 KB Execution killed with signal 13 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -