oj.uz

Submission #312541

# Submission time Handle Problem Language Result Execution time Memory
312541 2020-10-13T16:48:53 Z model_code Zagrade (COI20_zagrade) C++17
100 / 100
 1037 ms 1084 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

bool query(int l, int r) {
    cout << "? " << l + 1 << ' ' << r + 1 << endl;
    bool ans;
    cin >> ans;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    
    string sol(n, 0);
    stack<int> S;

    for (int i = 0; i < n; i++) {
        if (!S.empty() && query(S.top(), i)) {
            sol[S.top()] = '(';
            sol[i] = ')';
            S.pop();
        } else {
            S.push(i);
        }
    }

    int k = S.size();
    assert(k % 2 == 0);
    for (int i = 0; i < k; i++) {
        if (i < k / 2) sol[S.top()] = '(';
        else sol[S.top()] = ')';
        S.pop();
    }

    cout << "! " << sol << endl;

    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 12 ms 384 KB Output is correct
3 Correct 8 ms 396 KB Output is correct
4 Correct 13 ms 384 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 369 ms 544 KB Output is correct
3 Correct 839 ms 488 KB Output is correct
4 Correct 897 ms 480 KB Output is correct
5 Correct 827 ms 484 KB Output is correct
6 Correct 802 ms 556 KB Output is correct
7 Correct 1037 ms 772 KB Output is correct
8 Correct 803 ms 488 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 997 ms 916 KB Output is correct
3 Correct 771 ms 648 KB Output is correct
4 Correct 911 ms 860 KB Output is correct
5 Correct 915 ms 776 KB Output is correct
6 Correct 928 ms 1084 KB Output is correct
7 Correct 873 ms 948 KB Output is correct
8 Correct 830 ms 480 KB Output is correct