Submission #640290

#	Time	Username	Problem	Language	Result	Execution time	Memory
640290		kebine	Zagrade (COI20_zagrade)	C++17	57 / 100	1536 ms	1552 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, q, x, a[100069], pi, np, ng, byk = 0;
stack<long long> stk;

int main() {
  nyahalo
  long long i, j;
  cin >> n >> q;
  np = n/2;
  ng = n/2;
  for (i=1; i<=n; i++) {
    a[i] = 0;
  }
  if(q == n-1) {
    a[1] = 1;
    stk.push(1);
    for (i=2; i<=n; i++) {
      if (stk.empty()) {
        stk.push(i);
        a[i] = 1;
      } else {
        pi = stk.top();
        cout << "? " << pi << " " << i << "\n" << flush;
        cin >> x;
        if (x == 1) {
          a[i] = -1;
          stk.pop();
        } else {
          a[i] = 1;
          stk.push(i);
        }
      }
    }
    cout << "! ";
    for (i=1; i<=n; i++) {
      if (a[i] == 1) {
        cout << "(";
      } else {
        cout << ")";
      }
    }
    cout << "\n" << flush;
    otsumiko
  }
  for (i=2; i<=n; i+=2) {
    for (j=1; j<=n-i+1; j++) {
      cout << "? " << j << " " << j+i-1 << "\n" << flush;;
      cin >> x;
      byk++;
      if (x == 1) {
        if (a[j] == 0) {
          np--;
        }
        a[j] = 1;
        if (a[j+i-1] == 0) {
          ng--;
        }
        a[j+i-1] = -1;
      }
    }
  }
  for (i=1; i<=n; i++) {
    if (a[i] == 0) {
      if (ng>0) {
        a[i] = -1;
        ng--;
      } else {
        a[i] = 1;
        np--;
      }
    }
  }
  //cout << "byk: " << byk << "\n" << flush;
  cout << "! ";
  for (i=1; i<=n; i++) {
    if (a[i] == 1) {
      cout << "(";
    } else {
      cout << ")";
    }
  }
  cout << "\n" << flush;
  otsumiko
}

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