Submission #941039

#TimeUsernameProblemLanguageResultExecution timeMemory
941039hotboy2703Toxic Gene (NOI23_toxic)C++17
98.65 / 100
31 ms604 KiB
#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 timeMemoryGrader output
Fetching results...