Submission #940914

#	Time	Username	Problem	Language	Result	Execution time	Memory
940914		Tuanlinh123	Toxic Gene (NOI23_toxic)	C++17	21 / 100	10 ms	604 KiB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
mt19937_64 rng(170306);

void determine_type(ll n)
{
    ll lo=1, hi=n;
    auto queryrange=[&](ll l, ll r)
    {
        vector <ll> ask(r-l+1);
        iota(ask.begin(), ask.end(), l);
        return query_sample(ask);
    };
    while (hi>lo)
    {
        ll mid=(lo+hi)/2;
        if (queryrange(lo, mid)==mid-lo+1)
            lo=mid+1;
        else hi=mid;
    }
    vector <char> ans(n+1, 0);
    ans[lo]='T';
    for (ll i=1; i<=n; i+=8)
    {
        vector <ll> ask; ask.pb(lo);
        for (ll j=i; j<=n && j<i+8; j++)
            for (ll k=0; k<1<<(j-i); k++)
                ask.pb(j);
        ll x=query_sample(ask);
        for (ll j=i; j<=n && j<i+8; j++)
           if (x&1<<(j-i))
            ans[j]='S';
    }
    vector <ll> idx;
    for (ll i=1; i<=n; i++)
        if (!ans[i])
            idx.pb(i);
    shuffle(idx.begin(), idx.end(), rng);
    if (idx.size()<=200)
    {
        for (ll i:idx)
        {
            vector <ll> ask(1, i);
            if (query_sample(ask)) ans[i]='R';
            else ans[i]='T';
        }
    }
    else
    {
        auto queryran=[&](ll l, ll r)
        {
            vector <ll> ask;
            for (ll i=l; i<=r; i++)
                ask.pb(idx[i]);
            return query_sample(ask);
        };
        function <void(ll, ll)> find=[&](ll l, ll r)
        {
            ll x=queryran(l, r);
            if (x>0)
            {
                for (ll i=l; i<=r; i++)
                    ans[idx[i]]='R';
                return;
            }
            if (l==r) {ans[idx[l]]='T'; return;}
            ll mid=(l+r)/2;
            find(l, mid), find(mid+1, r);
        }; find(0, sz(idx)-1);
    }
    for (ll i=1; i<=n; i++)
        answer_type(i, ans[i]);
}

• Subtask 1: 21 / 100