| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 640249 | makanhulia | Zagrade (COI20_zagrade) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
const ll N = 1e5+5, MOD = 1e9+7, M = 1e3+5;
ll tc = 1, n, m, ar[N], br[N], str[M][M];
ll x, y, k, open = 0, close = 0;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> v;
ll ask(ll l, ll r){
// if(ar[l] != -1 && ar[r] != -1 && (r-l) == 1){
// if (ar[l] == 0 && ar[r] == 1) return 1;
// return 0;
// }
cout << "? " << l << " " << r << endl;
ll dum; cin >> dum;
return dum;
}#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
const ll N = 1e5+5, MOD = 1e9+7, M = 1e3+5;
ll tc = 1, n, m, ar[N], br[N], str[M][M];
ll x, y, k, open = 0, close = 0;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> v;
ll ask(ll l, ll r){
// if(ar[l] != -1 && ar[r] != -1 && (r-l) == 1){
// if (ar[l] == 0 && ar[r] == 1) return 1;
// return 0;
// }
cout << "? " << l << " " << r << endl;
ll dum; cin >> dum;
return dum;
}
void input(){
cin >> n >> k;
}
void answ(){
cout << "! ";
repp(i,1,n){
if (ar[i] == 0) cout << "(";
else cout << ")";
}
cout << endl;
}
void sub12(){
memset(str,-1,sizeof(str));
memset(ar,-1,sizeof(ar));
repp(i,1,n){
repp(j,i+1,n){
if ((j-i)%2){
str[i][j] = ask(i,j);
if (str[i][j] == 1){
ar[i] = 0;
ar[j] = 1;
}
}
}
}
answ();
}
void sub3(){
ll l = 1, r = n;
memset(ar,-1,sizeof(ar));
while(l < r){
ll a1 = ask(l,r);
if (a1 == 1){
ar[l] = 0;
ar[r] = 1;
l++;
r--;
continue;
}
else{
ll a2 = ask(l-1,l);
//1 -> 0 1
//0 -> 0 0
if (a2 == 1){
ar[l] = 1;
}
else ar[l] = 0;
//1 -> 0 1
//0 -> 1 1
ll a3 = ask(r,r+1);
if (a3 == 1){
ar[r] = 0;
}
else ar[r] = 1;
if (ar[l] && ar[r] == 0){
l++;
r--;
if (l < r){
ar[l] = 0;
ar[r] = 1;
l++;
r--;
}
}
else if (ar[l] && ar[r]){
l++;
// if (l >= r) break;
ar[l] = 0;
l++;
}
else{
r--;
// if (l >= r) break;
ar[r] = 1;
r--;
}
}
}
answ();
}
void solve(){
if (n <= 1e3) sub12();
else sub3();
//answ();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//cin >> tc;
while(tc--){
input();
solve();
}
}
void input(){
cin >> n >> k;
}
void answ(){
cout << "! ";
repp(i,1,n){
if (ar[i] == 0) cout << "(";
else cout << ")";
}
cout << endl;
}
void sub12(){
memset(str,-1,sizeof(str));
memset(ar,-1,sizeof(ar));
repp(i,1,n){
repp(j,i+1,n){
if ((j-i)%2) str[i][j] = ask(i,j);
if (str[i][j] == 1){
ar[i] = 0;
ar[j] = 1;
}
}
}
answ();
}
void sub3(){
ll l = 1, r = n;
memset(ar,-1,sizeof(ar));
while(l < r){
ll a1 = ask(l,r);
if (a1 == 1){
ar[l] = 0;
ar[r] = 1;
l++;
r--;
continue;
}
else{
ll a2 = ask(l-1,l);
//1 -> 0 1
//0 -> 0 0
if (a2 == 1){
ar[l] = 1;
}
else ar[l] = 0;
//1 -> 0 1
//0 -> 1 1
ll a3 = ask(r,r+1);
if (a3 == 1){
ar[r] = 0;
}
else ar[r] = 1;
if (ar[l] && ar[r] == 0){
l++;
r--;
if (l < r){
ar[l] = 0;
ar[r] = 1;
l++;
r--;
}
}
else if (ar[l] && ar[r]){
l++;
// if (l >= r) break;
ar[l] = 0;
l++;
}
else{
r--;
// if (l >= r) break;
ar[r] = 1;
r--;
}
}
}
answ();
}
void solve(){
if (n <= 1e3) sub12();
else sub3();
//answ();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//cin >> tc;
while(tc--){
input();
solve();
}
}