Submission #559101

#	Time	Username	Problem	Language	Result	Execution time	Memory
559101		Redhood	Zagrade (COI20_zagrade)	C++14	100 / 100	762 ms	848 KiB

zagrade

#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
using namespace std;

typedef long long ll;
typedef long double ld;


bool ask(int i , int j){
    cout << "? " << i + 1 << ' ' << j + 1 << endl;
    int ans;
    cin >> ans;
    return ans;
}
signed main(){
    int n , q;
    cin >> n >> q;

    stack < int > pos;

    pos.push(0);



    string s = string(n,  '(');

    int did=0;

    int need = n / 2;

//    cout << s << endl;
    for(int i = 1; i < n; ++i){
        if(pos.empty()){
            pos.push(i);
            continue;
        }
        int f = pos.top();

        if(ask(f , i)){
            s[f] = '(';
            s[i] = ')';
            did++;
            pos.pop();
        }else{
            pos.push(i);
        }
    }


    assert(sz(pos) % 2 == 0);
    int f = sz(pos) / 2;

    for(int t=0;t<f;++t){
        s[pos.top()] = '(';
        pos.pop();
    }
    for(int t=0;t<f;++t){
        s[pos.top()] = ')';
        pos.pop();
    }
    cout << "! " << s << endl;

    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:34:9: warning: unused variable 'need' [-Wunused-variable]
   34 |     int need = n / 2;
      |         ^~~~

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