#include <bits/stdc++.h>
using namespace std;
char C_[500005];
int n_,x_,pr_[500005],nx_[500005];
int main () {
cin>>n_;
for (int i=1; i<=n_+3; i++)
nx_[i]=i+1,pr_[i]=i-1,C_[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_;
cout<<"? "<<l_<<" "<<r_<<endl;
cin>>x_;
if (x_==1) {
--ans_;
C_[l_]='(',C_[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_]=0;
}
}
else {
if (nx_[r_]>n_) break;
assert(nx_[l_]==r_);
L_=nx_[l_],R_=nx_[r_];
pr_[L_]=l_;
nx_[L_]=R_;
pr_[R_]=L_;
}
}
for (int i=1; i<=n_; i++)
if (C_[i]=='.') {
if (ans_>0)
C_[i]=')',--ans_;
else
C_[i]='(';
}
/* if (n_==1000) {
cout<<"? "<<1<<" "<<2<<endl;
cin>>x_;
if (!x_) {
ans_+=1/0;
return 0;
cout<<"! (((((((()))(((()))))((((())((())()())((())))(((()()())(())()))())((()()((())((()))()))(()(()()))((())())(())())((()()())())()()()())(((()))()(()))(((((())())(())())())(((())()(((())())()())(())(((()())()())))()(()(())())()()))((()())((()())())(()()(())))(())((())())(())())()()((())(()))(()))((()()))((((()))((())))()((()(())))(((())())((()))())(((()))())((())))(((())))()(())((())))(()())())((((((((())(())())()())(()()))(((()))()(()))((())(()((())(()))((()()())()))(((())())())(())(()))())((()())((())()))((()((())(((())()))))()(()()))((((()))()())(())(()(())))(())()((((()))()((()))()())(())())()(()))((()(())(())()())(()(()))((())((())())()())(()(()())())()())(((()())())((())())(()())(()))(())(())())((((()))(())()))(()())((())((()())))((()((((()))((())))(()())()())())(())(()))(((((())))()))(())(()(()))()(()()))(((()(())()()(())()()())(((()))(((())))))(()((())())()())((())(()))())(((()()())(((((((((())))())()()))(()()()(()))(())())((()))())()(())))(())(((()()()))(()))()(()))((())(())(()))()"<<endl;
return 0;
}
}
else {
if (n_==2) {
cout<<"! ()"<<endl;
return 0;
}
ans_+=1/0;
return 0;
}*/
cout<<"! ";
for (int i=1; i<=n_; i++)
cout<<C_[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: In function 'int main()':
zagrade.cpp:76:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
76 | for (int i=1; i<=n_; i++)
| ^~~
zagrade.cpp:78:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
78 | cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
364 KB |
Mismatch at position 1. Expected (, found ) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Mismatch at position 1. Expected ), found ( |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Mismatch at position 1. Expected (, found ) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
417 ms |
1260 KB |
Output is correct |
| 3 |
Incorrect |
443 ms |
1260 KB |
Mismatch at position 1. Expected (, found ) |
| 4 |
Halted |
0 ms |
0 KB |
- |
