Submission #712438

#	Time	Username	Problem	Language	Result	Execution time	Memory
712438		noedit	Zagrade (COI20_zagrade)	C++17	0 / 100	3026 ms	4768 KiB

zagrade

#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;

#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

bool ask(int l, int r)
{
    cout << "? " << l << " " << r << endl;
    int b;
    cin >> b;
    return b;
}

const int MAXN = 1e5 + 10;

bool check[MAXN];
char ans[MAXN];
int lt[MAXN], rt[MAXN];

void solve()
{
    int n, k;
    cin >> n >> k;
    int res = 0;
    fill(ans, ans + n + 1, '#');
    fill(lt, lt + n + 1, -1);
    fill(rt, rt + n + 1, -1);
    queue<pair<int, int> > q;
    for (int i = 1; i < n; i++)
    {
        check[i] = ask(i, i + 1);
        if (check[i])
        {
            res++;
            ans[i] = '(';
            lt[i] = i + 1;
            ans[i + 1] = ')';
            rt[i + 1] = i;
            q.push({i, i + 1});
        }
    }
    if (res == 0)
    {
        for (int i = 1; i <= n / 2; i++) ans[i] = ')';
        for (int i = n / 2 + 1; i <= n; i++) ans[i] = '(';
    }
    else
    {
        while (!q.empty())
        {
            auto [l, r] = q.front();
            q.pop();
            if (l - 1 >= 1 && r + 1 <= n)
            {
                int lts = l - 1, rts = r + 1;
                    if (ans[l - 1] != '#')
                    {
                        lts = lt[l - 1] - 1;
                    }
                    if (ans[r + 1] != '#')
                    {
                        rts = rt[r + 1];
                    }
                    rt[lts] = rts;
                    ans[lts] = '(';
                    lt[rts] = lts;
                    ans[rts] = ')';
                    q.push({lts, rts});
            }
        }
    }
    cout << "! ";
    for (int i = 1; i <= n; i++) cout << ans[i];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

/*
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
*/

/*
1 1 1
100000000 1 1 1
1 1
*/

/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 7
• Subtask 3: 0 / 57
• Subtask 4: 0 / 22