oj.uz

Submission #679927

# Submission time Handle Problem Language Result Execution time Memory
679927 2023-01-09T16:16:24 Z Cyanmond Zagrade (COI20_zagrade) C++17
71 / 100
 864 ms 588 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;

    // valid sequence
    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;
        }
    }
    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 208 KB Output is correct
3 Correct 11 ms 280 KB Output is correct
4 Correct 9 ms 328 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 7 ms 288 KB Output is correct
7 Correct 8 ms 208 KB Output is correct
8 Correct 5 ms 300 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Mismatch at position 1. Expected ), found 0
2 Halted 0 ms 0 KB -

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 428 ms 508 KB Output is correct
3 Correct 864 ms 512 KB Output is correct
4 Correct 793 ms 512 KB Output is correct
5 Correct 784 ms 512 KB Output is correct
6 Correct 855 ms 504 KB Output is correct
7 Correct 617 ms 588 KB Output is correct
8 Correct 847 ms 508 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Mismatch at position 1. Expected ), found 0
2 Halted 0 ms 0 KB -