Submission #442564

#	Time	Username	Problem	Language	Result	Execution time	Memory
442564		fskarica	Zagrade (COI20_zagrade)	C++14	100 / 100	1119 ms	1084 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second

const int MAX = 1e5 + 10;
int n, q;
int x;
vector <int> v;
int arr[MAX];

int main() {
    cin >> n >> q;

    v.push_back(1);

    for (int i = 2; i <= n; i++) {
        if (v.size() == 0) {
            v.push_back(i);
            continue;
        }

        cout << "? " << v.back() << " " << i << endl;
        cin >> x;

        if  (x == 0) {
            v.push_back(i);
        }
        else {
            arr[i] = 2;
            arr[v.back()] = 1;
            v.pop_back();
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 0) {
            cnt++;
        }
    }
    cnt /= 2;


    cout << "! ";
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 1) {
            cout << "(";
        }
        else if (arr[i] == 2) {
            cout << ")";
        }
        else {
            if (cnt) {
                cout << ")";
                cnt--;
            }
            else {
                cout << "(";
            }
        }
    }
    cout << endl;

    return 0;
}

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