Submission #1205380

#TimeUsernameProblemLanguageResultExecution timeMemory
1205380biankToxic Gene (NOI23_toxic)C++20
45.48 / 100
8 ms548 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 find_toxic(int l, int r){ if(l>r) return {}; vi vec(r-l+1); iota(all(vec),l); 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.insert(begin(res),hi); return res; } const int k=8; void determine_type(int n){ memo.clear(); vi toxic; for(int l=1,r=k;l<=n;l=r+1,r=l+k-1){ for(int x:find_toxic(l,min(r,n))) toxic.pb(x); } 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...