Submission #320393

#	Time	Username	Problem	Language	Result	Execution time	Memory
320393		phathnv	Zagrade (COI20_zagrade)	C++11	100 / 100	996 ms	1008 KiB

zagrade

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Zagrade"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;

int n, q;
char res[N];
stack <int> s;

bool ask(int l, int r){
    cout << "? " << l << ' ' << r << endl << flush;
    int res;
    cin >> res;
    return res;
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        if (s.empty()){
            s.push(i);
            continue;
        }
        if (ask(s.top(), i)){
            res[s.top()] = '(';
            res[i] = ')';
            s.pop();
        } else {
            s.push(i);
        }
    }
    int sz = s.size();
    for(int i = 1; i <= sz / 2; i++){
        res[s.top()] = '(';
        s.pop();
    }
    for(int i = 1; i <= sz / 2; i++){
        res[s.top()] = ')';
        s.pop();
    }
    cout << "! " << string(res + 1, res + 1 + n) << endl << flush;
    return 0;
}

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