Submission #977757

#	Time	Username	Problem	Language	Result	Execution time	Memory
977757		CSQ31	Toxic Gene (NOI23_toxic)	C++17	93.25 / 100	12 ms	544 KiB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand2(int l,int r){return uniform_int_distribution<int>(l,r)(seed);}
vector<int>tox;
vector<int>leftover;
vector<int>notox;

int bquery(vector<int>v){
    int ori = sz(v);
    int c = min(8,sz(notox));

    vector<int>add;
    for(int i=0;i<c;i++){
        int x = notox.back();
        add.push_back(x);
        notox.pop_back();
        for(int j=0;j<(1<<i);j++)v.push_back(x);
    }

    int res = query_sample(v);
    if(res == sz(v)){
        for(int x:add)notox.push_back(x);
        return ori;
    }else{
        for(int i=0;i<c;i++){
            if(res & (1<<i))answer_type(add[i],'S');
            else answer_type(add[i],'R');
        }
        return 0;
    }
}
void find_toxic(vector<int>v){
   // for(int x:v)cout<<x<<" ";
   // cout<<'\n';
    if(sz(v) == 1){
        //cout<<v[0]<<'\n';
        answer_type(v[0],'T');
        tox.push_back(v[0]);
        return;
    }
    int m = sz(v)/2;
    vector<int>a,b;
    for(int i=0;i<m;i++)a.push_back(v[i]);
    for(int i=m;i<sz(v);i++)b.push_back(v[i]);
	if(rand2(0,1))swap(a,b);

    int res = bquery(a);
    if(res == sz(a)){ 
		for(int x:a)answer_type(x,'R');	
		find_toxic(b);
	}
    else {
		for(int x:b)leftover.push_back(x);
		find_toxic(a);
    }
}
void determine_type(int n){
	vector<int>p;
	for(int i=1;i<=n;i++)p.push_back(i);
	shuffle(p.begin(),p.end(),seed);
    notox.clear();
    tox.clear();

 vector<vector<int>>maybe;

    for(int i=1;i<=n;i+=8){
        vector<int>v;
        for(int j=0;j<8;j++){
            if(i+j > n)break;
            for(int k=0;k<(1<<j);k++)v.push_back(p[i+j-1]);
        }
        int res = query_sample(v);
        if(res == sz(v)){
            for(int j=0;j<8;j++){
                if(i+j > n)break;
                notox.push_back(p[i+j-1]);
            }
        }else{
            vector<int>u;
            for(int j=0;j<8;j++){
                if(i+j > n)break;
                if(res & (1<<j))answer_type(p[i+j-1],'S');
                else u.push_back(p[i+j-1]);
            }
            maybe.push_back(u);
        }
    }
	while(!maybe.empty()){
		vector<int>v = maybe.back();
		maybe.pop_back();
		int lim = 8;
		//if(sz(tox) >= 15)lim = 16;
		//if(sz(tox) >= 20)lim = 32;
		
		while(!maybe.empty() && sz(v) + sz(maybe.back()) <= lim){
			vector<int>u = maybe.back();
			for(int x:u)v.push_back(x);
			maybe.pop_back();
		}
		while(true){
            leftover.clear();
            find_toxic(v);
            v = leftover;
            if(v.empty())break;
            if(bquery(v)){
                for(int x:v)answer_type(x,'R');
                break;
            }
        }
	}


    //query left out regular/strong
    while(!notox.empty()){
        vector<int>v;
        int c = min(8,sz(notox));

        vector<int>add;
        for(int i=0;i<c;i++){
            int x = notox.back();
            add.push_back(x);
            notox.pop_back();
            for(int j=0;j<(1<<i);j++)v.push_back(x);
        }
        v.push_back(tox[0]);
        int res = query_sample(v);
        for(int i=0;i<c;i++){
            if(res & (1<<i))answer_type(add[i],'S');
            else answer_type(add[i],'R');
        }
    }
}

• Subtask 1: 93.25 / 100