Submission #1154413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154413		chthonic_cream	Zagrade (COI20_zagrade)	C++20	0 / 100	1 ms	432 KiB

zagrade

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long

using namespace __gnu_pbds;
using namespace std;
const int maxn=2e5;
const int maxm=1e3;
const int di[4]={-1, 0, 1, 0};
const int dj[4]={0, 1, 0, -1};
const ll mod=1e9+9;
typedef pair<ll, ll> pll;
struct PairCompare {
    bool operator()(const pll &a, const pll &b) const {
        return (a.first == b.first) ? a.second < b.second : a.first < b.first;
    }
};
typedef tree<
    pll,
    null_type,
    PairCompare,
    rb_tree_tag,
    tree_order_statistics_node_update>
ordered_multiset;

ll mulmod(ll a, ll b, ll mod) {
    ll res = 0;
    a = a % mod;
    while (b > 0) {
        if (b % 2 == 1)
            res = (res + a) % mod;
        a = (a * 2) % mod;
        b = b / 2;
    }
    return res % mod;
}

ll powmod(ll base, ll expo, ll mod) {
    ll res = 1;
    base = base % mod;
    while (expo > 0) {
        if (expo % 2 == 1)
            res = mulmod(res, base, mod);
        base = mulmod(base, base, mod);
        expo = expo / 2;
    }
    return res;
}

bool miller_rabin(ll n, ll d) {
    ll a = 2 + rand() % (n - 4);
    ll x = powmod(a, d, n);

    if (x == 1 || x == n - 1)
        return true;

    while (d != n - 1) {
        x = mulmod(x, x, n);
        d = d * 2;

        if (x == 1)
            return false;
        if (x == n - 1)
            return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}) {
        if (n % p == 0)
            return n == p;
    }

    ll d = n - 1;
    while (d % 2 == 0)
        d = d / 2;

    for (int i = 0; i < 10; i++) {
        if (!miller_rabin(n, d))
            return false;
    }
    return true;
}

class DSU
{
    vector<ll> rank, parent;
    public:
    DSU(ll x)
    {
        rank.resize(x, 0);
        parent.resize(x);
        for (int i=0; i<x; i++)
        {
            parent[i]=i;
        }
    }
    ll find(ll x)
    {
        ll root=parent[x];
        if (parent[root] != root)
        {
            return parent[x]=find(root);
        }
        return root;
    }
    void uni(ll x, ll y)
    {
        ll xroot=find(x);
        ll yroot=find(y);
        if (xroot == yroot)
        {
            return;
        }
        if (rank[xroot] < rank[yroot])
        {
            parent[xroot]=yroot;
        }
        else if (rank[xroot] > rank[yroot])
        {
            parent[yroot]=xroot;
        }
        else
        {
            parent[yroot]=xroot;
            rank[xroot]++;
        }
    }
};
vector<ll> PickUnique(ll n)
{
    //int a[n], last=n+1, temp;
    for (int i=0; i<n; i++)
    {
        //temp=UniqueCount(i, n);
        //if ()
    }
    return {0};
}
void procedure()
{
    ll n, q, verdict;
    cin>>n>>q;
    vector<ll> v, ans(n+1);
    for (int i=1; i<=n; i++)
    {
        if (v.empty())
        {
            v.push_back(i);
        }
        else
        {
            auto it=v.end();
            it--;
            cout<<"? "<<*it<<" "<<i;
            flush(cout);
            cin>>verdict;
            if (verdict)
            {
                ans[*it]=2;
                ans[i]=1;
                v.pop_back();
            }
            else
            {
                v.push_back(i);
            }
        }
    }
    if (!v.empty())
    {
        ll length=v.size();
        for (int i=0; i<length/2; i++)
        {
            ans[v[i]]=1;
        }
        for (int i=(length/2); i<length; i++)
        {
            ans[v[i]]=2;
        }
    }
    cout<<"! ";
    for (int i=1; i<=n; i++)
    {
        if (ans[i]==0)
        {
            cout<<"W";
        }
        if (ans[i]==1)
        {
            cout<<")";
        }
        if (ans[i]==2)
        {
            cout<<"(";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    t=1;
    while (t--)
    {
        procedure();
    }
    return 0;
}

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