oj.uz

Submission #381459

# Submission time Handle Problem Language Result Execution time Memory
381459 2021-03-25T08:06:25 Z VEGAnn Zagrade (COI20_zagrade) C++14
21 / 100
 3000 ms 776 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){
    q--;

    if (q < 0){
        while (1) {}
    }

    cout << "? " << a + 1 << " " << b + 1 << 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 = 1; 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 == 0 || r == n - 1) 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 11 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 12 ms 364 KB Output is correct
6 Correct 10 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 14 ms 364 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 7 ms 364 KB Output is correct
3 Correct 15 ms 364 KB Output is correct
4 Correct 15 ms 364 KB Output is correct
5 Correct 15 ms 492 KB Output is correct
6 Correct 10 ms 364 KB Output is correct
7 Correct 9 ms 364 KB Output is correct
8 Correct 14 ms 364 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 557 ms 620 KB Output is correct
3 Execution timed out 3015 ms 492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 966 ms 620 KB Output is correct
3 Execution timed out 3073 ms 776 KB Time limit exceeded
4 Halted 0 ms 0 KB -