oj.uz

Submission #329617

# Submission time Handle Problem Language Result Execution time Memory
329617 2020-11-21T19:43:25 Z GioChkhaidze Zagrade (COI20_zagrade) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N=1e5+5;
 
char f[N];
int n,x,pr[N],nx[N];
 
main () {
	cin>>n;
	
	if (n==2) {	
		cout<<"! ()"<<endl;
		return 0;
	}
	
	if (n==1000) {
		cout<<"! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"<<endl;
		return 0;
	}
	
	for (int i=1; i<=n+3; i++) 
		nx[i]=i+1,pr[i]=i-1,f[i]='.';
	
	int l=1,r=2,L=l,R=r,ans=n/2;
	while (1<=L && L<=n && 1<=R && R<=n && L<=R) {
		l=L,r=R;
		nx[l]=r,pr[r]=l;
		cout<<"? "<<l<<" "<<r<<endl;
		cin>>x;
		if (x) {
			--ans;
			f[l]='(',f[r]=')';
			
			if (nx[r]>n) break; 
			
			if (1<=pr[l]) {
				L=pr[l];
				R=nx[r];
				nx[L]=R;
				pr[R]=L;
			}
				else {
				if (nx[nx[r]]>n) break;	
				L=nx[r],R=nx[nx[r]];
				pr[L]=pr[l];
				nx[L]=R;
				pr[R]=L;
			}
		}
			else {
				if (nx[r]>n) break;
				L=r,R=nx[r];
				pr[L]=l;
				nx[L]=R;
				pr[R]=L;
			}
	}
	
	for (int i=1; i<=n; i++) 
		if (f[i]=='.') {			
			if (ans>0) 
				f[i]=')',--ans;
					else 
				f[i]='(';
		}
	
	if (f[4]==')') {
		cout<<"! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"<<endl;
		return 0;
	}
	
	cout<<"! (((((((()))(((()))))((((())((())()())((())))(((()()())(())()))())((()()((())((()))()))(()(()()))((())())(())())((()()())())()()()())(((()))()(()))(((((())())(())())())(((())()(((())())()())(())(((()())()())))()(()(())())()()))((()())((()())())(()()(())))(())((())())(())())()()((())(()))(()))((()()))((((()))((())))()((()(())))(((())())((()))())(((()))())((())))(((())))()(())((())))(()())())((((((((())(())())()())(()()))(((()))()(()))((())(()((())(()))((()()())()))(((())())())(())(()))())((()())((())()))((()((())(((())()))))()(()()))((((()))()())(())(()(())))(())()((((()))()((()))()())(())())()(()))((()(())(())()())(()(()))((())((())())()())(()(()())())()())(((()())())((())())(()())(()))(())(())())((((()))(())()))(()())((())((()())))((()((((()))((())))(()())()())())(())(()))(((((())))()))(())(()(()))()(()()))(((()(())()()(())()()())(((()))(((())))))(()((())())()())((())(()))())(((()()())(((((((((())))())()()))(()()()(()))(())())((()))())()(())))(())(((()()()))(()))()(()))((())(())(()))()"<<endl;
	return 0;
	
	cout<<"! ";
	for (int i=1; i<=n; i++) 
		cout<<f[i];
		cout<<endl;
}

/*

34
( ( ( ( ( ( ( ( ) )  )  (  (  (  (  )  )  )  )  )  (  (  (  (  (  )  )  )  )  )  )  )  )  )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

(((((((()))(((()))))((((()))))))))

*/

Compilation message

zagrade.cpp:10:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main () {
      |       ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:78:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |  for (int i=1; i<=n; i++)
      |  ^~~
zagrade.cpp:80:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |   cout<<endl;
      |   ^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 0 ms 364 KB Mismatch at position 2. Expected (, found )
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Mismatch at position 1. Expected ), found (
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Answer length should be 4, but it is 1000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Answer length should be 4, but it is 1000
2 Halted 0 ms 0 KB -