# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
941039 | hotboy2703 | Toxic Gene (NOI23_toxic) | C++17 | 31 ms | 604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(1);
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll ans[310];
ll wow = 0;
ll query(vector <ll> all){
wow++;
return query_sample(all);
}
ll cnt_poison = 0;
//0 thuong 1 doc 2 manh
vector <ll> ukn;
void solve(vector <ll> all){
if (sz(all) == 1){ans[all.back()]=1;cnt_poison++;return;}
ll mid = sz(all)/2;
vector <ll> L;
vector <ll> R;
for (ll i = 0;i < mid;i++)L.push_back(all[i]);
for (ll i = mid;i < sz(all);i ++)R.push_back(all[i]);
vector <ll> sus=L;
ll ok = -1;
for (ll j = 0;j < 8 && j < sz(ukn);j ++){
if (sz(sus) + MASK(j) * sz(L) <= 300){
for (ll k = 0;k < MASK(j) * sz(L);k ++){
sus.push_back(ukn[sz(ukn)-1-j]);
}
ok = j;
}
}
// assert(sz(sus) <= 300);
ll tmp = query(sus);
// ll tmp2 = query(L);
// if ((tmp2!=sz(L))!=(tmp!=sz(sus))){
// cout<<"DUMB"<<endl;
// for (auto x:sus)cout<<x<<' ';
// cout<<endl;
// for (auto x:L)cout<<x<<' ';
// cout<<endl;
// cout<<tmp<<' '<<tmp2<<endl;
// cout<<sz(sus)<<' '<<sz(L)<<endl;
// for (auto x:sus)if(query({x})==0){cout<<x<<endl;};
// cout<<sz(ukn)<<endl;
// for (auto x:ukn){cout<<x<<' ';assert(query({x}));}
// cout<<endl;
// assert(0);
// }
if (tmp!=sz(sus)){
for (ll j = 0;j <= ok;j ++){
if (BIT(tmp/sz(L),j)){ans[ukn[sz(ukn)-1-j]] = 2;}
else ans[ukn[sz(ukn)-1-j]] = 0;
}
for (ll i = 0;i <= ok;i ++)ukn.pop_back();
solve(L);
}
else solve(R);
}
void determine_type(int n){
wow = 0;
cnt_poison = 0;
for (ll i = 1;i <= n;i ++)ans[i] = -1;
ukn.clear();
deque <ll> pos;
for (ll i= 1;i <= n;i ++){
pos.push_back(i);
}
ll init_strong = 0;
ll strong = 0;
ll cnt_norm = 0;
{
strong = query(vector <ll> (pos.begin(),pos.end()));
init_strong = strong;
}
while (sz(pos)&&cnt_poison<30){
shuffle(pos.begin(),pos.end(),rng);
vector <ll> cur;
while (sz(pos) && sz(cur) < 8){cur.push_back(pos.back());pos.pop_back();}
vector <ll> all;
for (ll j= 0 ;j < sz(cur);j ++){
for (ll k= 0 ;k < MASK(j);k ++)all.push_back(cur[j]);
}
ll sus = query(all);
if (sus != sz(all)){
vector <ll> tmp;
for (ll j = 0;j < sz(cur);j ++){
if (BIT(sus,j)){ans[cur[j]] = 2;strong--;}
else tmp.push_back(cur[j]);
}
cur = tmp;
solve(cur);
bool ok = 0;
for (auto x:cur){
if (ans[x] == 1){ok = 1;continue;}
if (!ok){cnt_norm++;ans[x] = 0;}
else pos.push_front(x);
}
}
else{
for (auto x:cur){ukn.push_back(x);}
}
}
ll nor = n - cnt_poison - init_strong;
ll poison = -1;
vector <ll> rem;
for (ll i = 1;i <= n;i ++){
if (ans[i] == 1){
poison = i;
}
else{
if (ans[i] == -1)rem.push_back(i);
}
}
while (sz(rem)&&strong>0&&cnt_norm<nor){
shuffle(rem.begin(),rem.end(),rng);
vector <ll> cur;
while (sz(rem) && sz(cur) < 8){cur.push_back(rem.back());rem.pop_back();}
vector <ll> all;
for (ll j = 0;j < sz(cur);j ++){
for (ll k = 0;k < MASK(j);k ++){
all.push_back(cur[j]);
}
}
all.push_back(poison);
ll x = query(all);
for (ll j = 0;j < sz(cur);j ++){
if (BIT(x,j)){
ans[cur[j]] = 2;
strong--;
}
else {cnt_norm++;ans[cur[j]] = 0;}
}
}
for (ll i = 1;i <= n;i ++)if (ans[i]==-1)ans[i] = (cnt_norm<nor)?0:2;
for (ll i = 1;i <= n;i ++){
if (ans[i]==0)answer_type(i,'R');
if (ans[i]==2)answer_type(i,'S');
if (ans[i]==1)answer_type(i,'T');
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |