oj.uz

Submission #320895

# Submission time Handle Problem Language Result Execution time Memory
320895 2020-11-10T07:51:03 Z dolphingarlic Zagrade (COI20_zagrade) C++14
100 / 100
 1036 ms 996 KB 
#include <bits/stdc++.h>
using namespace std;

bool guess(int a, int b) {
    cout << "? " << a << ' ' << b << endl;
    bool res;
    cin >> res;
    return res;
}

char ans[100001];

int main() {
    int n, q, rem;
    cin >> n >> q;
    rem = n / 2;
    stack<int> stck;
    for (int i = 1; i <= n; i++) {
        if (!stck.size()) stck.push(i);
        else if (guess(stck.top(), i)) {
            ans[stck.top()] = '(';
            ans[i] = ')';
            stck.pop();
            rem--;
        } else stck.push(i);
    }
    cout << "! ";
    for (int i = 1; i <= n; i++) {
        if (ans[i] == '(' || ans[i] == ')') cout << ans[i];
        else if (rem) {
            cout << ')';
            rem--;
        } else cout << '(';
    }
    cout << endl;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 11 ms 364 KB Output is correct
6 Correct 6 ms 492 KB Output is correct
7 Correct 10 ms 384 KB Output is correct
8 Correct 9 ms 384 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 11 ms 364 KB Output is correct
3 Correct 9 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 8 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 385 ms 672 KB Output is correct
3 Correct 1036 ms 752 KB Output is correct
4 Correct 871 ms 788 KB Output is correct
5 Correct 814 ms 876 KB Output is correct
6 Correct 908 ms 740 KB Output is correct
7 Correct 748 ms 996 KB Output is correct
8 Correct 906 ms 888 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 812 ms 964 KB Output is correct
3 Correct 967 ms 696 KB Output is correct
4 Correct 853 ms 740 KB Output is correct
5 Correct 805 ms 680 KB Output is correct
6 Correct 678 ms 796 KB Output is correct
7 Correct 684 ms 772 KB Output is correct
8 Correct 893 ms 740 KB Output is correct