Submission #1205384

#TimeUsernameProblemLanguageResultExecution timeMemory
1205384biankToxic Gene (NOI23_toxic)C++20
47.35 / 100
10 ms544 KiB
#include <bits/stdc++.h> #include "toxic.h" using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; map<vi,int> memo; int cnt=0; int query(vi v){ if(memo.count(v)) return memo[v]; return memo[v]=query_sample(v); } vi perm; vi find_toxic(int l, int r){ if(l>r) return {}; vi vec(r-l+1); forsn(i,l,r+1) vec[i-l]=perm[i]; if(query(vec)==r-l+1) return {}; int lo=l-1,hi=r; while(hi-lo>1){ int mid=(lo+hi)/2; if(query(vi(begin(vec),begin(vec)+mid-l+1))<mid-l+1) hi=mid; else lo=mid; } vi res=find_toxic(hi+1,r); res.pb(perm[hi]); return res; } const int k=8; void determine_type(int n){ memo.clear(); vi toxic; perm=vi(n); forn(i,n) perm[i]=i+1; srand(time(0)^clock()); random_shuffle(all(perm)); for(int l=0,r=k;l<n;l=r+1,r=l+k-1){ for(int x:find_toxic(l,min(r,n-1))) toxic.pb(x); } sort(all(toxic)); for(int x:toxic) answer_type(x,'T'); vi unknown; int j=0; forsn(i,1,n+1){ if(j<sz(toxic)&&toxic[j]==i){ j++; }else{ unknown.pb(i); } } while(!unknown.empty()){ vi type(8,-1); forn(i,8){ if(unknown.empty()) break; type[i]=unknown.back(); unknown.pop_back(); } vi sample{toxic[0]}; forn(i,8) if(type[i]!=-1){ forn(_,1<<i) sample.eb(type[i]); } int x=query(sample); forn(i,8) if(type[i]!=-1){ if(x>>i&1) answer_type(type[i],'S'); else answer_type(type[i],'R'); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...