oj.uz

Submission #318492

# Submission time Handle Problem Language Result Execution time Memory
318492 2020-11-02T07:00:52 Z kshitij_sodani Zagrade (COI20_zagrade) C++14
100 / 100
 1094 ms 1324 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'
//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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 10 ms 364 KB Output is correct
6 Correct 10 ms 364 KB Output is correct
7 Correct 10 ms 364 KB Output is correct
8 Correct 10 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 8 ms 364 KB Output is correct
4 Correct 9 ms 364 KB Output is correct
5 Correct 8 ms 364 KB Output is correct
6 Correct 10 ms 364 KB Output is correct
7 Correct 11 ms 364 KB Output is correct
8 Correct 11 ms 364 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 428 ms 944 KB Output is correct
3 Correct 793 ms 948 KB Output is correct
4 Correct 853 ms 876 KB Output is correct
5 Correct 811 ms 956 KB Output is correct
6 Correct 810 ms 1096 KB Output is correct
7 Correct 817 ms 1184 KB Output is correct
8 Correct 810 ms 892 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 831 ms 1324 KB Output is correct
3 Correct 801 ms 1180 KB Output is correct
4 Correct 877 ms 1260 KB Output is correct
5 Correct 1094 ms 972 KB Output is correct
6 Correct 637 ms 1296 KB Output is correct
7 Correct 809 ms 1288 KB Output is correct
8 Correct 998 ms 1008 KB Output is correct