oj.uz

Submission #381451

# Submission time Handle Problem Language Result Execution time Memory
381451 2021-03-25T08:02:11 Z VEGAnn Zagrade (COI20_zagrade) C++14
0 / 100
 2 ms 492 KB 
#include <bits/stdc++.h>
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
set<i2> st;
string s;
int n, q;

int query(int a, int b){
    cout << "? " << a << " " << b << endl;

    int res; cin >> res;

    return res;
}

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

#ifdef _LOCAL
//    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    s = "";

    for (int i = 0; i < n; i++)
        s += "?";

    for (int i = 2; i <= n; ){
        int res = query(i - 1, i);

        if (!res){
            i++;
        } else {
            int l = i - 1, r = i;

            s[l] = '(';
            s[r] = ')';

            while (1){
                while (sz(st) > 0){
                    i2 cr = (*(--st.end()));

                    if (cr[1] + 1 != l) break;

                    l = cr[0];

                    st.erase(cr);
                }

                if (l == 1 || r == n) break;

                res = query(l - 1, r + 1);

                if (!res) break;

                s[l - 1] = '(';
                s[r + 1] = ')';

                l--; r++;
            }

            i = r + 1;

            st.insert({l, r});
        }
    }

    int cnt = 0;

    for (int i = 0; i < sz(s); i++)
        cnt += bool(s[i] == '?');

    assert(cnt % 2 == 0);

    cnt /= 2;

    for (int i = 0; i < sz(s); i++)
        if (s[i] == '?'){
            s[i] = (cnt > 0 ? '(' : ')');
            cnt--;
        }

    cout << "! " << s << endl;

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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