oj.uz

Submission #559101

# Submission time Handle Problem Language Result Execution time Memory
559101 2022-05-09T11:34:11 Z Redhood Zagrade (COI20_zagrade) C++14
100 / 100
 762 ms 848 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 9 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 9 ms 208 KB Output is correct
8 Correct 8 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 10 ms 304 KB Output is correct
5 Correct 7 ms 288 KB Output is correct
6 Correct 9 ms 208 KB Output is correct
7 Correct 9 ms 208 KB Output is correct
8 Correct 7 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 392 ms 384 KB Output is correct
3 Correct 667 ms 460 KB Output is correct
4 Correct 574 ms 380 KB Output is correct
5 Correct 491 ms 380 KB Output is correct
6 Correct 762 ms 380 KB Output is correct
7 Correct 700 ms 840 KB Output is correct
8 Correct 719 ms 384 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 744 ms 848 KB Output is correct
3 Correct 584 ms 576 KB Output is correct
4 Correct 623 ms 688 KB Output is correct
5 Correct 745 ms 564 KB Output is correct
6 Correct 693 ms 740 KB Output is correct
7 Correct 654 ms 628 KB Output is correct
8 Correct 742 ms 376 KB Output is correct