Submission #1206420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206420		Captain_Georgia	Zagrade (COI20_zagrade)	C++20	100 / 100	236 ms	1148 KiB

zagrade

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

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, Q;
    cin >> N >> Q;

    auto ask = [&](int a, int b) -> int {
        assert(Q --);
        cout << "? " << a << " " << b << endl;
        int res;
        cin >> res;
        return res;
    };
    string S(N, ')');
    vector<int> st;
    for (int i = 1;i <= N;i ++) {
        if (st.size() == 0) {
            st.push_back(i);
        } else if (ask(st.back(), i) == 1) {
            S[i - 1] = ')';
            S[st.back() - 1] = '(';
            st.pop_back();
        } else {
            st.push_back(i);
        }
    }
    int l = 0, r = st.size() - 1;
    while (l < r) {
        S[st[l ++] - 1] = ')';
        S[st[r --] - 1] = '(';
    }
    assert(l > r);
    cout << "! " << S << endl;
}

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