Submission #706432

#	Time	Username	Problem	Language	Result	Execution time	Memory
706432		vjudge1	Zagrade (COI20_zagrade)	C++17	100 / 100	985 ms	10248 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const ll mxN = 5e5;
int n,q;
set<int>bf;
set<int>ind;
int main(){
  cin >>n>>q;
  int rem = n;
  char s[mxN];
  for(int i =1 ;i <= n;i++) {bf.insert(i);ind.insert(i - 1);}
  for(int i = 2;i <= n;i++){
    auto x = bf.lower_bound(i);
    if(x == bf.begin()) i++;
    x = bf.lower_bound(i);
    x--;
    int j  = *x;
    cout.flush()<<"? "<<j<<' '<<i<<endl;
    bool cr;
    cin>>cr;
    // for(auto x : bf){
    //   cout<<x<<' ';
    // }
    // cout<<endl;
    if(cr == 1){
      bf.erase(i);
      bf.erase(j);
      ind.erase(i - 1);
      ind.erase(j - 1);
      s[i - 1] = ')';
      s[j - 1] = '(';
      rem -= 2;
    }
  }
  int cnt = 0;
  for(auto x : ind){
    cnt++;
    if(cnt > rem / 2) s[x] = '(';
    else s[x] = ')';
  }
  cout.flush()<<"! "<<s<<endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 7 / 7
• Subtask 3: 57 / 57
• Subtask 4: 22 / 22