Submission #1152338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152338		itslq	Zagrade (COI20_zagrade)	C++20	0 / 100	136 ms	512 KiB

zagrade

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

vector<char> ans;

bool query(int l, int r) {
    bool v;
    cout << "? " << ++l << " " << ++r << endl;
    cin >> v;
    return v;
}

void solve(int l, int r) {
    if (l >= r) return;

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

    bool L, R;
    if (l + 1 == r) return;

    L = query(l, l + 1);
    R = query(r - 1, r);

    ans[l + 1] = L;
    ans[r - 1] = !R;

    if (L && R) {
        ans[l + 1] = ')';
        ans[r - 1] = '(';
        solve(l + 2, r - 2);
    } else if (L) {
        ans[l + 1] = ')';
        ans[r - 1] = ')';
        // ans[l + 2] = '(';
        solve(l + 2, r);
    } else if (R) {
        ans[l + 1] = '(';
        ans[r - 1] = '(';
        // ans[r - 2] = ')';
        solve(l, r - 2);
    } else {
        ans[l + 1] = '(';
        ans[r - 1] = ')';
        solve(l + 2, r - 2);
    }
}

int main() {
    int N, Q;
    cin >> N >> Q;
    ans = vector<char>(N, '-');
    solve(0, N - 1);

    cout << "! ";
    for (int i = 0; i < N; i++) cout << ans[i];
}

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