oj.uz

Submission #1018517

# Submission time Handle Problem Language Result Execution time Memory
1018517 2024-07-10T06:26:25 Z kukuk Zagrade (COI20_zagrade) C++14
0 / 100
 630 ms 6712 KB 
#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] = ')';
                }
            }
        }
      	cout << "! ";
        for(int i = 1; i <= n; i++){
            cout << ar[i];
        }
      cout << endl;
    }
 
}
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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Incorrect 6 ms 344 KB Mismatch at position 9. Expected ), found (
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 630 ms 6712 KB Output is correct
3 Incorrect 601 ms 6640 KB Mismatch at position 15. Expected ), found (
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -