Submission #1018476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018476		kukuk	Zagrade (COI20_zagrade)	C++14	0 / 100	1 ms	344 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int ukr = 1e5+10;
ll n, m, id, a, b;
char ar[ukr];
map<pair<int,int>, int> mp;
int ask(int a, int b){
    cout << "? " << a << " " << b << endl;
    int kkl;
    cin >> kkl;
    return kkl;
}
void rec(int l, int r){
    if(r-l == 1){
        int vl = ask(l, r);
        mp[{l, r}] = vl;
        if(vl){
            ar[l] = '(';
            ar[r] = ')';
        }
        return;
    }
    int mid = (l+r)/2;
    int vl = ask(l, r);
    mp[{l, r}] = vl;
    if((mid-l+1)%2){
        mid--;
    }
    rec(l, mid);
    rec(mid+1, r);
    if(vl){
        if(mp[{l, mid}] && mp[{mid+1, r}]){
            return;
        }
        if(mp[{l, mid}]){
            int tgh = r-(mid+1)+1;
            tgh/=2;
            for(int i = mid+1; i < mid+1+tgh; i++){
                ar[i] = '(';
            }
            for(int i =  mid+1+tgh; i <= r ; i++){
                ar[i] = ')';
            }
        }else if(mp[{mid+1, r}]){
            int tgh = mid-l+1;
            tgh/=2;
            for(int i = l; i < l+tgh; i++){
                ar[i] = '(';
            }
            for(int i = l+tgh; i <= mid; i++){
                ar[i] = ')';
            }
        }else{
            int tgh = r-l+1;
            tgh /= 2;
            for(int i = l; i < l+tgh; i++){
                ar[i] = '(';
            }
            for(int i = l+tgh; i <= r; i++){
                ar[i] = ')';
            } 
        }
    }
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        ar[i] = '.';
    }
    rec(1, n);
    if(mp[{1, n}]){
        int totl = 0, totr = 0;
        for(int i = 1; i <= n; i++){
            if(ar[i] == '('){
                totl++;
            }else if(ar[i] == ')'){
                totr++;
            }
        }
        for(int i = 1; i <= n; i++){
            if(ar[i] == '.'){
                if(totl < n/2){
                    totl++;
                    ar[i] = '(';
                }else{
                    totr++;
                    ar[i] = ')';
                }
            }
        }
        for(int i = 1; i <= n; i++){
            cout << ar[i];
        }
    }

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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