Submission #1152499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152499		jmuzhen	Zagrade (COI20_zagrade)	C++20	71 / 100	266 ms	6824 KiB

zagrade

// https://oj.uz/problem/view/COI20_zagrade
// try to grab 'entire sequence is valid' subtasks

/* let's start over. what if we just naively match brackets? so we know the sequence is valid for this subtask
 * and so s[0] is (. then we must have some ) matching s[0]. like ()<- or (()())<- . also, since the sequence is valid,
 * notice that if [0,i] matches then i is definitely ).
 * we can tell if [0,i] matches if query(0,i) is 1. but what if it is 0 ? Then 0,i doesn't match. this means that even though
 * 0,i might be ( and ) respectively, They don't match because i is matched to some other (. same as simple bracket matching.
 * on the other hand, if query(0,i) is 1 then 0, i "match" because i is the correct match for 0.
 * what does this mean?
 * since sequence is valid then every element must match to _SOMETHING_. it can be a starting point or an ending point.
 * lets fix the starting point at 0 first. then to find its match we can query every element 1,2,3,...,n until we get a 1.
 * then this is O(N^2) if we repeat for every element. but wait, can we repeat this for every element? say in ((())),
 * 0 matches with 6. then we go to 1, it matches with 5, etc. that works. but what if it's an extreme case.
 * say ()()(). wait that works also.
 * say (())(). then 0 matches with 3.
 * wait, why am I using 0-indexing? whatever, we will continue to use 0 indexing from now on.
 * say (())(). then 0 matches with 3, then go on to 1. 1 matches with 2. then go on to 4. 4 matches with 5.
 * so i think this works but it's O(N^2) queries.
 *
 * can we improve?
 * - 1. obviously every query should have an even length otherwise its always 0.
 *      - so we can optimise this in query function itself, just return 0 if length is odd
 * - why is this current method O(N^2) ? oh, because we may need to traverse the entire sequence to match for each one.
 * say ((())), we need to go through the entire string to get the answer for 0, 1, etc.
 * how to improve this?
 * what if we copy bracket matching method. in bracket matching naively searching for a pair is also O(N^2) right.
 * so bracket matching uses a stack. so it's not eager to find the match for a specific starting point now, it pushes it onto
 * the stack and tries to find the match later.
 * so we shouldnt fix the starting point!
 * we should fix the ending point!
 * but how to do that?
 * say we have a stack, its empty at first.
 * OHHH! because if the stack is empty that means we are at index 0 and that means we are definitely an open bracket
 * that means we can just push 0 on the stack and look for a mtch later.
 * then when 1 comes, how do we check if its a match?
 * just run a query. query(0, 1)
 * if this is 1 then we just match them and continue on. (decomposed the problem)
 * if its 0 then that means 1 must be ( and we push 1 on the stack.
 * but wait, is this generalisable to long sequence?
 * but wait, at least this optimises it. because we dont need to check with 0 anymore, we can just
 * check with the LAST element of the stack! because of how bracket matching works. always matches the inner bracket first,
 * if it doesnt match inner bracket it cannot match outer bracket. so we can just skip.
 * i think this works. so only O(N) queries!
 * so if we see a element that gives a query result of 1 with the top stack element, we just match it with that,
 * and then pop both off the stack.
 * i think this works.
 *
 *
 *
 */
#include <bits/stdc++.h>
using namespace std;

int n, q;

map<pair<int, int>, int> query_memo; // optimisation

// helpers to query & output
inline int query(int i, int j) {
  if (query_memo[{i,j}]) {
    return query_memo[{i, j}];
  }
  if ((j - i + 1) % 2 == 1) {
    return 0;
  }

  cout << "? " << i << " " << j << endl;
  int r; cin >> r;
  return query_memo[{i,j}] = r;
}
inline int query(int i, int j, const vector<int>& input) {
  return query(input[i], input[j]);
}

inline void output(vector<short>&s) {
  cout << "! ";
  for (int i = 1; i <= n; i++) {
    cout << (s[i] == 0 ? '(' : ')');
  }
  cout << endl;
}

inline void output(vector<char>&s) {
  cout << "! ";
  for (int i = 1; i <= n; i++) {
    cout << s[i];
  }
  cout << endl;
}

int main() {
    cin >> n >> q;
    vector<char> out(n+1);

    stack<int> st;

    for (int i = 1; i <= n; i++) {
      if (st.empty()) {
        out[i] = '(';
        st.push(i); continue;
      }

      int p = st.top();
      int res = query(p, i);
      if (res == 1) {
        // match
        st.pop();
        out[p] = '(';
        out[i] = ')';
      }
      else {
        // is open because otherwise, it would be a match
        out[i] = '(';
        st.push(i);
      }
    }

    output(out);
}

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