Submission #381460

#	Time	Username	Problem	Language	Result	Execution time	Memory
381460		VEGAnn	Zagrade (COI20_zagrade)	C++14	100 / 100	1070 ms	1260 KiB

zagrade

#include <bits/stdc++.h>
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
set<i2> st;
string s;
int n, q;

int query(int a, int b){
    q--;

    if (q < 0){
        while (1) {}
    }

    cout << "? " << a + 1 << " " << b + 1 << endl;

    int res; cin >> res;

    return res;
}

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

#ifdef _LOCAL
//    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    s = "";

    for (int i = 0; i < n; i++)
        s += "?";

    for (int i = 1; i < n; ){
        int res = query(i - 1, i);

        if (!res){
            i++;
        } else {
            int l = i - 1, r = i;

            s[l] = '(';
            s[r] = ')';

            while (1){
                while (sz(st) > 0){
                    i2 cr = (*(--st.end()));

                    if (cr[1] + 1 != l) break;

                    l = cr[0];

                    st.erase(cr);
                }

                if (l == 0 || r == n - 1) break;

                res = query(l - 1, r + 1);

                if (!res) break;

                s[l - 1] = '(';
                s[r + 1] = ')';

                l--; r++;
            }

            i = r + 2;

            st.insert({l, r});
        }
    }

    int cnt = 0;

    for (int i = 0; i < sz(s); i++)
        cnt += bool(s[i] == '?');

    assert(cnt % 2 == 0);

    cnt /= 2;

    for (int i = 0; i < sz(s); i++)
        if (s[i] == '?'){
            s[i] = (cnt > 0 ? ')' : '(');
            cnt--;
        }

    cout << "! " << s << endl;

    return 0;
}

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