Submission #1150815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150815		fryingduc	Zagrade (COI20_zagrade)	C++20	100 / 100	237 ms	1048 KiB

zagrade

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, q;
int cnt_asks;
string s;

int ask(int l, int r) {
  ++l, ++r;
  ++cnt_asks;
  #ifdef duc_debug
  stack<int> st;
  for (int i = l; i <= r; ++i) {
    if (s[i] == ')') {
      if (st.empty()) return 0;
      st.pop();
    } else {
      st.push(i);
    }
  }
  return st.empty();
  #else
  cout << "? " << l << " " << r << endl;
  int x; cin >> x;
  return x;
  #endif
}

void answer(string res) {
  #ifdef duc_debug
  res = ' ' + res;
  if (res != s) {
    cout << "WA";
    assert(0);
  } else {
    if (cnt_asks > q) {
      cout << "too many calls " << cnt_asks << endl;
      assert(0);
    }
    cout << cnt_asks << endl;
  }
  #else
  cout << "! " << res << endl;
  #endif
}

void solve() {
  #ifdef duc_debug
    cin >> n >> q >> s;
    s = ' ' + s;
  #else
    cin >> n >> q;
  #endif
  
  stack<int> st;
  string res;
  for (int i = 1; i <= n; ++i) {
    res += '?';
  }
  st.push(0);
  for (int i = 1; i < n; ++i) {
    if (st.empty()) {
      st.push(i);
      continue;
    } else {
      int t = st.top();
      if (ask(t, i)) {
        res[t] = '(', res[i] = ')';
        st.pop();
      } else {
        st.push(i);
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (res[i] != '?') continue;
    ++cnt;
    if (cnt <= (int)st.size() / 2) {
      res[i] = ')';
    } else {
      res[i] = '(';
    }
  }
  answer(res);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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