oj.uz

Submission #940995

# Submission time Handle Problem Language Result Execution time Memory
940995 2024-03-08T04:48:26 Z Tuanlinh123 Toxic Gene (NOI23_toxic) C++17
68.95 / 100
 11 ms 756 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)
{
    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, cnt=30;
    auto queryran=[&](ll l, ll r)
    {
        vector <ll> ask;
        for (ll i=l; i<=r; i++)
            ask.pb(idx[i]);
        return query_sample(ask);
    };
    while (sz(idx) && cnt)
    {
        vector <ll> left;
        for (ll i=0; i<8 && sz(idx); i++)
            left.pb(idx.back()), idx.pop_back();
        vector <ll> ask;
        for (ll j=0; j<sz(left); j++)
            for (ll k=0; k<1<<j; k++)
                ask.pb(left[j]);
        ll x=query_sample(ask);
        if (x==ask.size()) continue;
        vector <ll> left1;
        for (ll j=0; j<sz(left); j++)
        {
            if (x&1<<j) ans[left[j]]='S';
            else left1.pb(left[j]);
        }
        ll p=0, en=sz(left1)-1;
        auto queryran=[&](ll l, ll r)
        {
            vector <ll> ask;
            for (ll i=l; i<=r; i++)
                ask.pb(left1[i]);
            return query_sample(ask);
        };
        ll lo=0, hi=en;
        while (hi>lo)
        {
            ll mid=(lo+hi)/2;
            if (queryran(lo, mid)==mid-lo+1) lo=mid+1;
            else hi=mid;
        }
        ans[left1[lo]]='T', cnt--, toxic=left1[lo];
        for (ll j=0; j<lo; j++) ans[left1[j]]='R';
        for (ll j=lo+1; j<sz(left1); j++) idx.pb(left1[j]);
    }
    idx.clear();
    for (ll i=1; i<=n; i++)
        if (!ans[i]) idx.pb(i);
    shuffle(idx.begin(), idx.end(), rng);
    ll sum=query_sample(idx);
    for (ll i=0; i<sz(idx) && sum; 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', sum--;
            else ans[idx[j]]='R';
        }
    }
    for (ll i=1; i<=n; i++)
    {
        if (ans[i]) answer_type(i, ans[i]);
        else answer_type(i, 'R');
    }
}

Compilation message

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

Subtask #1
68.95 / 100.0

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