oj.uz

Submission #640290

# Submission time Handle Problem Language Result Execution time Memory
640290 2022-09-14T05:56:07 Z kebine Zagrade (COI20_zagrade) C++17
57 / 100
 1536 ms 1552 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Runtime error 1536 ms 316 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Mismatch at position 1. Expected ), found (
2 Halted 0 ms 0 KB -

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 368 ms 1084 KB Output is correct
3 Correct 789 ms 1096 KB Output is correct
4 Correct 809 ms 1108 KB Output is correct
5 Correct 572 ms 1196 KB Output is correct
6 Correct 678 ms 1084 KB Output is correct
7 Correct 706 ms 1552 KB Output is correct
8 Correct 651 ms 1088 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Mismatch at position 1. Expected ), found (
2 Halted 0 ms 0 KB -