Submission #1148913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148913		fatman87878	Toxic Gene (NOI23_toxic)	C++20	28.92 / 100	6 ms	328 KiB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int blk = 8;

void determine_type(int n){
	mt19937 rng(time(0));
	int toxic;
	vector<int> idx(n),nottoxic,isstrong(n+1),istoxic(n+1);
	iota(all(idx),1);
	//shuffle(all(idx),rng);
	for(;!idx.empty();){
		int R = min((int)idx.size(),blk);
		vector<int> ask;
		for(int cnt = 0,k = 0;k<R;k++,cnt++){
			for(int j = 0;j<1<<cnt;j++)ask.emplace_back(idx[k]);
		}
		int ret = query_sample(ask);
		if(ret!=ask.size()){
			ask.clear();
			for(int k = R;k--;){
				if(ret>>k&1)isstrong[idx[k]] = 1,idx.erase(idx.begin()+k);
				else ask.emplace_back(idx[k]);
			}
			reverse(all(ask));
			for(int l = 0,r = ask.size(),L = 0;l<ask.size();l++,L=l){
				r=ask.size();
				for(;l<r;){
					int mid=l+r>>1;
					if(query_sample(vector(ask.begin()+L,ask.begin()+mid+1)))l=mid+1;
					else r=mid;
				}
				if(l==ask.size())l--;
				else istoxic[toxic=ask[l]]=1;
				for(int i = L;i<=l;i++)idx.erase(idx.begin());
			}
		}
		else {
			for(;R--;)nottoxic.emplace_back(*idx.begin()),idx.erase(idx.begin());
		}
	}
	for(int i = 0;i<nottoxic.size();){
		vector<int> ask(1,toxic);
		for(int cnt = 0,k = i;cnt<8&&k<nottoxic.size();k++,cnt++){
			for(int j = 0;j<1<<cnt;j++)ask.emplace_back(nottoxic[k]);
		}
		int ret = query_sample(ask);
		for(int cnt = 0;cnt<8&&i<nottoxic.size();i++,cnt++,ret>>=1){
			isstrong[nottoxic[i]] = ret&1;
		}
	}
	for(int i = 1;i<=n;i++){
		if(istoxic[i])answer_type(i,'T');
		else if(isstrong[i])answer_type(i,'S');
		else answer_type(i,'R');
	}
}

// g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o toxic stub.cpp toxic.cpp

• Subtask 1: 28.9176 / 100