oj.uz

Submission #320393

# Submission time Handle Problem Language Result Execution time Memory
320393 2020-11-08T15:02:42 Z phathnv Zagrade (COI20_zagrade) C++11
100 / 100
 996 ms 1008 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Zagrade"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;

int n, q;
char res[N];
stack <int> s;

bool ask(int l, int r){
    cout << "? " << l << ' ' << r << endl << flush;
    int res;
    cin >> res;
    return res;
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        if (s.empty()){
            s.push(i);
            continue;
        }
        if (ask(s.top(), i)){
            res[s.top()] = '(';
            res[i] = ')';
            s.pop();
        } else {
            s.push(i);
        }
    }
    int sz = s.size();
    for(int i = 1; i <= sz / 2; i++){
        res[s.top()] = '(';
        s.pop();
    }
    for(int i = 1; i <= sz / 2; i++){
        res[s.top()] = ')';
        s.pop();
    }
    cout << "! " << string(res + 1, res + 1 + n) << endl << flush;
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 431 ms 888 KB Output is correct
3 Correct 876 ms 848 KB Output is correct
4 Correct 880 ms 1008 KB Output is correct
5 Correct 712 ms 764 KB Output is correct
6 Correct 841 ms 868 KB Output is correct
7 Correct 791 ms 740 KB Output is correct
8 Correct 791 ms 780 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 787 ms 976 KB Output is correct
3 Correct 882 ms 880 KB Output is correct
4 Correct 759 ms 808 KB Output is correct
5 Correct 914 ms 688 KB Output is correct
6 Correct 996 ms 744 KB Output is correct
7 Correct 832 ms 744 KB Output is correct
8 Correct 912 ms 804 KB Output is correct