Submission #1185451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185451		NotLinux	Toxic Gene (NOI23_toxic)	C++20	0 / 100	4 ms	580 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);
	int BSZ[n] , kalan = 30;
	vector<pair<int,vector<int>>>SR;
	for(int i = 0;i<n;i+=BSZ[i]){
		BSZ[i] = min(8 , (n-i+kalan-1)/kalan);
		if(__builtin_popcount(BSZ[i]) != 1)BSZ[i] = 1 << (__lg(BSZ[i]) + 1);
		// BSZ[i] = 8;
		vector<int>vec1;
		for(int j = i;j<min(n , i+BSZ[i]);j++){
			for(int k = 0;k<(1<<(j-i));k++)
				vec1.push_back(perm[j]);
		}
		int res1 = query_sample(vec1);
		if(res1 == vec1.size()){
			SR.push_back({i,vec1});
		}
		else{
			vector<int>vec;
			for(int j = i;j<min(n , i+BSZ[i]);j++){
				if(res1 & (1 << (j-i))){
					ans[perm[j]] = 2;
				}
				else vec.push_back(perm[j]);
			}
			do{
				int l = 0 , r = vec.size()-1;
				while(l < r){
					int mid = (l + r) / 2;
					vector<int>bruh;
					if(!SR.empty())bruh = SR.back().second;
					for(int k = l;k<=mid;k++)
						bruh.push_back(vec[k]);
					int res2 = query_sample(bruh);
					if(res2 != bruh.size()){
						r = mid;
						if(!SR.empty()){
							for(int j = SR.back().first;j<min(n,SR.back().first+BSZ[SR.back().first]);j++){
								if(res2 & (1 << (j-SR.back().first))){
									ans[perm[j]] = 2;
								}
								else ans[perm[j]] = 0;
							}
							SR.pop_back();
						}
					}
					else l = mid+1;
				}
				ans[vec[l]] = 1;
				kalan--;
				vec.erase(vec.begin() + l);
			}while(!vec.empty() and query_sample(vec) != vec.size());
		}
	}
	int toxic = -1;
	for(int i = 1;i<=n;i++)
		if(ans[i] == 1)
			toxic = i;
	while(!SR.empty()){
		SR.back().second.push_back(toxic);
		int res2 = query_sample(SR.back().second);
		for(int j = SR.back().first;j<min(n,SR.back().first+BSZ[SR.back().first]);j++){
			if(res2 & (1 << (j-SR.back().first))){
				ans[perm[j]] = 2;
			}
		}
		SR.pop_back();
	}
	for(int i = 1;i<=n;i++)
		if(ans[i] == -1)
			ans[i] = 0;
	for(int i = 1;i<=n;i++){
		if(ans[i] == 0){
			// cout << "R";
			answer_type(i,'R');
		}
		else if(ans[i] == 1){
			// cout << "T";
			answer_type(i,'T');
		}
		else {
			// cout << "S";
			answer_type(i,'S');
		}
	}
	// cout << endl;
}

• Subtask 1: 0 / 100