oj.uz

Submission #374555

# Submission time Handle Problem Language Result Execution time Memory
374555 2021-03-07T12:50:46 Z Alex_tz307 Zagrade (COI20_zagrade) C++17
100 / 100
 1008 ms 1292 KB 
#include <bits/stdc++.h>

using namespace std;

bool query(const int &i, const int &j) {
    cout << "? " << i + 1 << ' ' << j + 1 << endl;
    bool ans;
    cin >> ans;
    return ans;
}

int main() {
    int N, Q;
    cin >> N >> Q;
    string sol;
    sol.resize(N);
    vector<int> S;
    for(int i = 0; i < N; ++i) {
        if(S.empty()) {
            S.emplace_back(i);
            continue;
        }
        bool ans = query(S.back(), i);
        if(ans) {
            sol[S.back()] = '(';
            sol[i] = ')';
            S.pop_back();
        }
        else
            S.emplace_back(i);
    }
    for(int i = 0; i < (int)S.size(); ++i)
        if(i < (int)S.size() / 2)
            sol[S[i]] = ')';
        else
            sol[S[i]] = '(';
    cout << "! " << sol << endl;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 436 ms 492 KB Output is correct
3 Correct 1008 ms 472 KB Output is correct
4 Correct 769 ms 620 KB Output is correct
5 Correct 837 ms 492 KB Output is correct
6 Correct 861 ms 492 KB Output is correct
7 Correct 935 ms 876 KB Output is correct
8 Correct 886 ms 492 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 715 ms 1292 KB Output is correct
3 Correct 934 ms 960 KB Output is correct
4 Correct 745 ms 1108 KB Output is correct
5 Correct 884 ms 812 KB Output is correct
6 Correct 682 ms 1052 KB Output is correct
7 Correct 930 ms 796 KB Output is correct
8 Correct 850 ms 492 KB Output is correct