Submission #940982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
940982	2024-03-08T04:13:26 Z	Tuanlinh123	Toxic Gene (NOI23_toxic)	C++17	44.4471 / 100	10 ms	508 KB

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(11092001);
 
void determine_type(ll n)
{
    vector <char> ans(n+1, 0);
    vector <ll> idx(n);
    iota(idx.begin(), idx.end(), 1);
    shuffle(idx.begin(), idx.end(), rng);
    ll len=8, toxic=0;
    auto queryran=[&](ll l, ll r)
    {
        vector <ll> ask;
        for (ll i=l; i<=r; i++)
            ask.pb(idx[i]);
        return query_sample(ask);
    };
    for (ll i=0; i<sz(idx); i+=len)
    {
        vector <ll> ask;
        for (ll j=i; j<sz(idx) && j<i+len; j++)
            for (ll k=0; k<1<<(j-i); k++)
                ask.pb(idx[j]);
        ll x=query_sample(ask);
        if (x==ask.size()) continue;
        vector <ll> left;
        for (ll j=i; j<sz(idx) && j<i+len; j++)
        {
            if (x&1<<(j-i)) ans[idx[j]]='S';
            else left.pb(idx[j]);
        }
        ll p=0, en=sz(left)-1;
        auto queryran=[&](ll l, ll r)
        {
            vector <ll> ask;
            for (ll i=l; i<=r; i++)
                ask.pb(left[i]);
            return query_sample(ask);
        };
        while (1)
        {
            if (p>en) break;
            if (queryran(p, en)==en-p+1) break;
            ll lo=p, hi=en;
            while (hi>lo)
            {
                ll mid=(lo+hi)/2;
                if (queryran(p, mid)==mid-p+1) lo=mid+1;
                else hi=mid;
            } 
            ans[left[lo]]='T', p=lo+1, toxic=left[lo];
        }
        for (ll j=i; j<sz(idx) && j<i+len; j++)
            if (!ans[idx[j]])
                ans[idx[j]]='R';
    }
    idx.clear();
    for (ll i=1; i<=n; i++)
        if (!ans[i]) idx.pb(i);
    shuffle(idx.begin(), idx.end(), rng);
    for (ll i=0; i<sz(idx); i+=len)
    {
        vector <ll> ask; ask.pb(toxic);
        for (ll j=i; j<sz(idx) && j<i+len; j++)
            for (ll k=0; k<1<<(j-i); k++)
                ask.pb(idx[j]);
        ll x=query_sample(ask);
        for (ll j=i; j<sz(idx) && j<i+len; j++)
        {
            if (x&1<<(j-i)) ans[idx[j]]='S';
            else ans[idx[j]]='R';
        }
    }
    for (ll i=1; i<=n; i++)
        answer_type(i, ans[i]);
}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (x==ask.size()) continue;
      |             ~^~~~~~~~~~~~
toxic.cpp:21:10: warning: variable 'queryran' set but not used [-Wunused-but-set-variable]
   21 |     auto queryran=[&](ll l, ll r)
      |          ^~~~~~~~

Subtask #1

44.44705882 / 100.0

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