Submission #1148574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148574		fatman87878	Toxic Gene (NOI23_toxic)	C++20	21.92 / 100	8 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

void determine_type(int n){
	mt19937 rng(time(0));
	vector<int> idx(n+1),toxic,nottoxic,isstrong(n+1),istoxic(n+1);
	iota(all(idx),0);
	shuffle(idx.begin()+1,idx.end(),rng);
	auto chk = [&](auto self,int l,int r) -> void {
		if(l==r-1)return istoxic[toxic.emplace_back(idx[l])]=1,void();
		int mid = l+r>>1;
		if(query_sample(vector(idx.begin()+l,idx.begin()+mid))!=mid-l)
			self(self,l,mid);
		else 
			for(int i = l;i<mid;i++)nottoxic.emplace_back(idx[i]);
		if(query_sample(vector(idx.begin()+mid,idx.begin()+r))!=r-mid)
			self(self,mid,r);
		else 
			for(int i = mid;i<r;i++)nottoxic.emplace_back(idx[i]);
	};
	chk(chk,1,n+1);
	for(int i = 0;i<nottoxic.size();){
		vector<int> ask(1,toxic.front());
		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');
	}
}

• Subtask 1: 21.9231 / 100