oj.uz

Submission #381460

# Submission time Handle Problem Language Result Execution time Memory
381460 2021-03-25T08:06:59 Z VEGAnn Zagrade (COI20_zagrade) C++14
100 / 100
 1070 ms 1260 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 + 2;

            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 7 ms 364 KB Output is correct
3 Correct 10 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 10 ms 364 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 11 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 1 ms 364 KB Output is correct
2 Correct 8 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 10 ms 364 KB Output is correct
6 Correct 11 ms 364 KB Output is correct
7 Correct 11 ms 364 KB Output is correct
8 Correct 10 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 343 ms 620 KB Output is correct
3 Correct 1070 ms 620 KB Output is correct
4 Correct 900 ms 620 KB Output is correct
5 Correct 873 ms 616 KB Output is correct
6 Correct 739 ms 616 KB Output is correct
7 Correct 978 ms 620 KB Output is correct
8 Correct 988 ms 620 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 820 ms 616 KB Output is correct
3 Correct 957 ms 852 KB Output is correct
4 Correct 960 ms 1056 KB Output is correct
5 Correct 1036 ms 876 KB Output is correct
6 Correct 930 ms 1260 KB Output is correct
7 Correct 913 ms 876 KB Output is correct
8 Correct 981 ms 620 KB Output is correct