Submission #940982

#TimeUsernameProblemLanguageResultExecution timeMemory
940982Tuanlinh123Toxic Gene (NOI23_toxic)C++17
44.45 / 100
10 ms508 KiB
#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 (stderr)

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)
      |          ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...