Submission #941052

#	Time	Username	Problem	Language	Result	Execution time	Memory
941052		bachhoangxuan	Toxic Gene (NOI23_toxic)	C++17	93.25 / 100	28 ms	748 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);
    //reverse(p.begin(),p.end());
    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();
        /*
        cout << (int)cur.size() << '\n';
        for(int x:cur) cout << x << ' ';
        cout << total << '\n';
        */
        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<<i);

                int num=mid+1;
                vector<int> nxt;
                //cout << "all " << (int)all.size() << '\n';
                while(!all.empty() && num+(int)nxt.size()<8){
                    add(all.back(),1<<(num+(int)nxt.size()));
                    nxt.push_back(all.back());all.pop_back();
                }

                int cnt=ask(),real_cnt=cnt&((1<<num)-1);
                if(!real_cnt){
                    for(int i=0;i<(int)nxt.size();i++){
                        if(cnt>>(num+i)&1) c[nxt[i]]='S';
                        else c[nxt[i]]='R';
                    }
                }
                else all.insert(all.end(),nxt.begin(),nxt.end());
                cnt=real_cnt;
                //cout << "cnt " << cnt << '\n';
                if(cnt==0) pos=mid,r=mid-1;
                else l=mid+1;
            }

            //cout << '*' << pos << '\n';

            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: 93.25 / 100