oj.uz

Submission #318412

# Submission time Handle Problem Language Result Execution time Memory
318412 2020-11-01T18:37:34 Z kshitij_sodani Zagrade (COI20_zagrade) C++14
0 / 100
 1682 ms 2748 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;
		for(int i=0;i<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;
		}
		for(int i=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:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0;i<ss.size()-1;i++){
      |               ~^~~~~~~~~~~~
zagrade.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i=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 1532 ms 2748 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 364 KB Output is correct
2 Runtime error 1682 ms 2572 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 0 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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