Submission #1185400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185400		NotLinux	Toxic Gene (NOI23_toxic)	C++20	45.48 / 100	6 ms	328 KiB

toxic

#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void determine_type(int n){
	int perm[n];
	vector<int>ans(n+1,-1);
	iota(perm , perm + n , 1);
// 	shuffle(perm , perm + n , rng);
	// eliminate the toxic ones
	// cout << "NOLUO" << endl;
	const int BSZ = 8;
	for(int i = 0;i<n;i+=BSZ){
		vector<int>vec;
		for(int j = i;j<min(n , i+BSZ);j++){
			vec.push_back(perm[j]);
		}
		while(!vec.empty() and query_sample(vec) != vec.size()){
			int l = 0 , r = vec.size()-1;
			while(l < r){
				int mid = (l + r) / 2;
				vector<int>bruh;
				for(int k = l;k<=mid;k++)
					bruh.push_back(vec[k]);
				if(query_sample(bruh) != bruh.size())r = mid;
				else l = mid+1;
			}
			ans[vec[l]] = 1;
			// cout << "POISON : " << vec[l] << endl;
			vec.erase(vec.begin() + l);
		}
	}
	// cout << "NOLUO" << endl;
	int toxic = -1;
	for(int i = 1;i<=n;i++)
		if(ans[i] == 1)
			toxic = i;
	// cout << "toxic : " << toxic << endl;
	// cout << "		FLAG0" << endl;
	vector<int>v;
	for(int i = 0;i<n;i++)
		if(ans[perm[i]] == -1)
			v.push_back(perm[i]);
// 	shuffle(v.begin() , v.end() , rng);
	// cout << "v : ";for(auto itr : v)cout << itr << " ";cout << endl;
	// cout << "		FLAG1" << endl;
	// eliminate the strong ones
	// cout << "NOLUO" << endl;
	for(int i = 0;i<v.size();i+=8){
		vector<int>vec;
		for(int j = 0;j<8;j++){
			if(i+j>=v.size())continue;
			int tmp = 1 << j;
			while(tmp--)vec.push_back(v[i+j]);
		}
		vec.push_back(toxic);
		int cevap = query_sample(vec);
		for(int j = 0;j<8;j++){
			if(i+j<v.size() and (cevap & (1 << j)))
				ans[v[i+j]] = 2;
		}
	}
	// cout << "NOLUO" << endl;
	for(int i = 1;i<=n;i++)
		if(ans[i] == -1)
			ans[i] = 0;
	
	// cout << "		FLAG2" << endl;
	for(int i = 1;i<=n;i++){
		if(ans[i] == 0){
			answer_type(i,'R');
			// cout << "R";
		}
		else if(ans[i] == 1){
			answer_type(i,'T');
			// cout << "T";
		}
		else {
			answer_type(i,'S');
			// cout << "S";
		}
	}
	// cout << endl;
}

• Subtask 1: 45.4824 / 100