oj.uz

Submission #940934

# Submission time Handle Problem Language Result Execution time Memory
940934 2024-03-08T02:43:39 Z Tuanlinh123 Toxic Gene (NOI23_toxic) C++17
34.8706 / 100
 7 ms 508 KB 
#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';
    ll sum=queryrange(1, n);
    for (ll i=1; i<=n; i+=8)
    {
        if (!sum) break;
        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', sum--;
    }
    vector <ll> idx;
    for (ll i=1; i<=n; i++)
        if (!ans[i])
            idx.pb(i);
    shuffle(idx.begin(), idx.end(), rng);
    auto queryran=[&](ll l, ll r)
    {
        vector <ll> ask;
        for (ll i=l; i<r; i++)
            ask.pb(idx[i]);
        return query_sample(ask);
    };
    ll len=max(1, sz(idx)/80);
    for (ll i=0; i<sz(idx); i+=len)
    {
        ll x=queryran(i, min(sz(idx), i+len));
        if (x)
        {
            for (ll j=i; j<min(sz(idx), i+len); j++)
                ans[idx[j]]='R';
        }
        else if (min(sz(idx), i+len)-i==1) ans[idx[i]]='T';
        else
        {
            for (ll j=i; j<min(sz(idx), i+len); j++)
            {
                if (queryran(j, j+1)) ans[idx[j]]='R';
                else ans[idx[j]]='T';
            }
        }
    }
    for (ll i=1; i<=n; i++)
        answer_type(i, ans[i]);
}

Subtask #1
34.87058824 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 2 ms 348 KB Partially correct
3 Partially correct 4 ms 348 KB Partially correct
4 Partially correct 5 ms 348 KB Partially correct
5 Partially correct 3 ms 348 KB Partially correct
6 Partially correct 7 ms 348 KB Partially correct
7 Partially correct 5 ms 348 KB Partially correct
8 Partially correct 6 ms 344 KB Partially correct
9 Partially correct 6 ms 348 KB Partially correct
10 Partially correct 5 ms 348 KB Partially correct
11 Partially correct 5 ms 344 KB Partially correct
12 Partially correct 2 ms 348 KB Partially correct
13 Partially correct 5 ms 344 KB Partially correct
14 Partially correct 5 ms 344 KB Partially correct
15 Partially correct 4 ms 348 KB Partially correct
16 Partially correct 5 ms 508 KB Partially correct
17 Partially correct 5 ms 348 KB Partially correct
18 Partially correct 6 ms 504 KB Partially correct
19 Partially correct 6 ms 348 KB Partially correct
20 Partially correct 5 ms 508 KB Partially correct
21 Partially correct 5 ms 344 KB Partially correct
22 Correct 4 ms 348 KB Output is correct
23 Correct 4 ms 348 KB Output is correct
24 Partially correct 3 ms 348 KB Partially correct
25 Partially correct 3 ms 348 KB Partially correct
26 Partially correct 3 ms 348 KB Partially correct
27 Partially correct 4 ms 348 KB Partially correct
28 Partially correct 4 ms 348 KB Partially correct
29 Partially correct 3 ms 348 KB Partially correct
30 Partially correct 3 ms 348 KB Partially correct
31 Partially correct 4 ms 348 KB Partially correct
32 Partially correct 4 ms 348 KB Partially correct
33 Partially correct 4 ms 348 KB Partially correct
34 Partially correct 2 ms 348 KB Partially correct
35 Partially correct 3 ms 348 KB Partially correct
36 Partially correct 1 ms 348 KB Partially correct