Submission #1263122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263122		PagodePaiva	Zagrade (COI20_zagrade)	C++20	100 / 100	272 ms	5784 KiB

zagrade

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int query(int a, int b){
    cout << "? " << a << ' ' << b << '\n';
    cout << flush;
    int x;
    cin >> x;
    return x;
}

set <int> ativos;
int ans[N];

int main(){
    int n, q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        ativos.insert(i);
    }
    memset(ans, -1, sizeof ans);
    int cnt = n/2;
    for(int i = n-1;i >= 1;i--){
        int x = query(i, *ativos.upper_bound(i));
        if(x == 1){
            int v = *ativos.upper_bound(i);
            ans[i] = 0;
            ans[v] = 1;
            ativos.erase(i);
            ativos.erase(v);
            cnt--;
        }
    }
    string s;
    for(int i = 1;i <= n;i++){
        //cout << ans[i] << ' ';
        if(ans[i] == -1){
            if(cnt > 0){
                s.push_back(')');
                cnt--;
            }
            else{
                s.push_back('(');
            }
        }
        else if(ans[i] == 0){
            s.push_back('(');
        }
        else{
            s.push_back(')');
        }
    }
    cout << "! " << s << '\n';
    cout << flush;
}

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