Submission #941036

#	Time	Username	Problem	Language	Result	Execution time	Memory
941036		bachhoangxuan	Toxic Gene (NOI23_toxic)	C++17	67.60 / 100	23 ms	600 KiB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(69420);

vector<int> toxic;
void reset(){
    toxic.clear();
}
void add(int x,int cnt){
    for(int i=0;i<cnt;i++) toxic.push_back(x);
}
int ask(){
    return query_sample(toxic);
}

void determine_type(int n){
	vector<int> p(n);
    vector<char> c(n+1);
    iota(p.begin(),p.end(),1);
    vector<int> all;
    int T=0;
    while(!p.empty()){
        shuffle(p.begin(),p.end(),rng);
        vector<int> cur;
        for(int i=0;i<8;i++){
            if(p.empty()) break;
            cur.push_back(p.back());
            p.pop_back();
        }
        reset();
        int sz=(int)cur.size();
        for(int i=0;i<sz;i++) add(cur[i],(1<<i));
        int total=ask();

        if(total==(1<<sz)-1) all.insert(all.end(),cur.begin(),cur.end());
        else{
            for(int i=sz-1;i>=0;i--){
                if((total>>i)&1){
                    c[cur[i]]='S';
                    cur.erase(cur.begin()+i);
                }
            }
            sz=(int)cur.size();
            int l=0,r=sz-2,pos=sz-1;
            while(l<=r){
                int mid=(l+r)>>1;reset();
                for(int i=0;i<=mid;i++) add(cur[i],1);
                int cnt=ask();
                if(cnt==0) pos=mid,r=mid-1;
                else l=mid+1;
            }
            T=cur[pos];
            c[cur[pos]]='T';
            cur.erase(cur.begin()+pos);
            for(int i=pos-1;i>=0;i--){
                c[cur[i]]='R';
                cur.erase(cur.begin()+i);
            }
            p.insert(p.begin(),cur.begin(),cur.end());
        }
    }
    while(!all.empty()){
        vector<int> cur;
        for(int i=0;i<8;i++){
            if(all.empty()) break;
            cur.push_back(all.back());
            all.pop_back();
        }
        reset();
        add(T,1);
        int sz=(int)cur.size();
        for(int i=0;i<sz;i++) add(cur[i],(1<<i));
        int total=ask();
        for(int i=sz-1;i>=0;i--){
            if(total>>i&1) c[cur[i]]='S';
            else c[cur[i]]='R';
        }
    }
    //for(int i=1;i<=n;i++) cout << c[i];
    //cout << '\n';
    for(int i=1;i<=n;i++) answer_type(i,c[i]);
}

• Subtask 1: 67.60000000000001 / 100