oj.uz

Submission #948364

# Submission time Handle Problem Language Result Execution time Memory
948364 2024-03-18T04:53:22 Z NeroZein Zagrade (COI20_zagrade) C++17
100 / 100
 547 ms 2060 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

bool ask(int l, int r) {
  cout << "?" << ' ' << l << ' ' << r << endl; 
  bool ret;
  cin >> ret;
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<int> stk; 
  vector<char> ans(n + 1); 
  for (int r = 1; r <= n; ++r) {
    if (stk.empty()) {
      stk.push_back(r);
      continue; 
    }
    int l = stk.back();
    bool valid = ask(l, r);
    if (valid) {
      ans[l] = '(';
      ans[r] = ')';
      stk.pop_back();
    } else {
      stk.push_back(r); 
    }
  }
  int m = (int) stk.size();
  for (int i = 0; i < m / 2; ++i) {
    ans[stk[i]] = ')';
  }
  for (int i = m / 2; i < m; ++i) {
    ans[stk[i]] = '(';
  }
  cout << "! ";
  for (int i = 1; i <= n; ++i) {
    cout << ans[i];
  }
  cout << endl; 
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 596 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 234 ms 600 KB Output is correct
3 Correct 516 ms 600 KB Output is correct
4 Correct 473 ms 528 KB Output is correct
5 Correct 454 ms 548 KB Output is correct
6 Correct 471 ms 596 KB Output is correct
7 Correct 489 ms 1272 KB Output is correct
8 Correct 470 ms 600 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 486 ms 2060 KB Output is correct
3 Correct 467 ms 992 KB Output is correct
4 Correct 514 ms 1544 KB Output is correct
5 Correct 510 ms 1052 KB Output is correct
6 Correct 547 ms 1916 KB Output is correct
7 Correct 509 ms 1288 KB Output is correct
8 Correct 503 ms 532 KB Output is correct