oj.uz

Submission #679936

# Submission time Handle Problem Language Result Execution time Memory
679936 2023-01-09T16:25:03 Z Cyanmond Zagrade (COI20_zagrade) C++17
100 / 100
 847 ms 952 KB 
#include <bits/stdc++.h>

bool query(int l, int r) {
    std::cout << '?' << ' ' << l + 1 << ' ' << r << std::endl;
    int res;
    std::cin >> res;
    return res == 1;
}

void answer(std::string s) {
    std::cout << '!' << ' ' << s << std::endl;
    std::exit(0);
}

int main() {
    int N, Q;
    std::cin >> N >> Q;

    std::stack<int> stk;
    std::string ans(N, '0');
    int l = 0;
    for (int i = 1; i < N; ++i) {
        const int r = i + 1;
        const auto res = query(l, r);
        if (res) {
            ans[l] = '(';
            ans[i] = ')';
            if (stk.empty()) {
                l = i + 1;
                ++i;
            } else {
                l = stk.top();
                stk.pop();
            }
        } else {
            stk.push(l);
            l = i;
        }
    }

    const int count_zero = std::count(ans.begin(), ans.end(), '0');
    int c = 0;
    for (int i = 0; i < N; ++i) {
        if (ans[i] == '0') {
            ans[i] = c < count_zero / 2 ? ')' : '(';
            ++c;
        }
    }
    answer(ans);
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 11 ms 208 KB Output is correct
3 Correct 10 ms 300 KB Output is correct
4 Correct 15 ms 300 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 10 ms 208 KB Output is correct
8 Correct 9 ms 304 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 453 ms 504 KB Output is correct
3 Correct 656 ms 512 KB Output is correct
4 Correct 847 ms 508 KB Output is correct
5 Correct 700 ms 508 KB Output is correct
6 Correct 808 ms 508 KB Output is correct
7 Correct 802 ms 752 KB Output is correct
8 Correct 483 ms 508 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 519 ms 952 KB Output is correct
3 Correct 707 ms 680 KB Output is correct
4 Correct 831 ms 756 KB Output is correct
5 Correct 766 ms 556 KB Output is correct
6 Correct 489 ms 636 KB Output is correct
7 Correct 677 ms 508 KB Output is correct
8 Correct 578 ms 524 KB Output is correct