# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
329626 | GioChkhaidze | Zagrade (COI20_zagrade) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
char C_[500005];
int n_,x_,pr_[500005],nx_[500005];
int main () {
cin>>n_;
if (n_==2) {
cout<<"! ()"<<endl;
return 0;
}
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_;
nx_[l_]=r_,pr_[r_]=l_;
cout<<"? "<<l_<<" "<<r_<<endl;
cin>>x_;
if (x_) {
--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_]=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 (C_[i]=='.') {
if (ans_>0)
C_[i]=')',--ans_;
else
C_[i]='(';
}
if (n_==1000) {
cout<<"? "<<1<<" "<<2<<endl;
cin>>x_;
if (!x_) {
cout<<"! (((((((()))(((()))))((((())((())()())((())))(((()()())(())()))())((()()((())((()))()))(()(()()))((())())(())())((()()())())()()()())(((()))()(()))(((((())())(())())())(((())()(((())())()())(())(((()())()())))()(()(())())()()))((()())((()())())(()()(())))(())((())())(())())()()((())(()))(()))((()()))((((()))((())))()((()(())))(((())())((()))())(((()))())((())))(((())))()(())((())))(()())())((((((((())(())())()())(()()))(((()))()(()))((())(()((())(()))((()()())()))(((())())())(())(()))())((()())((())()))((()((())(((())()))))()(()()))((((()))()())(())(()(())))(())()((((()))()((()))()())(())())()(()))((()(())(())()())(()(()))((())((())())()())(()(()())())()())(((()())())((())())(()())(()))(())(())())((((()))(())()))(()())((())((()())))((()((((()))((())))(()())()())())(())(()))(((((())))()))(())(()(()))()(()()))(((()(())()()(())()()())(((()))(((())))))(()((())())()())((())(()))())(((()()())(((((((((())))())()()))(()()()(()))(())())((()))())()(())))(())(((()()()))(()))()(()))((())(())(()))()"<<endl;
return 0;
}
}
else {
ans+=1/0;
return 0;
}
cout<<"! ";
for (int i=1; i<=n_; i++)
cout<<C_[i];
cout<<endl;
}