Submission #1185155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185155		NotLinux	Toxic Gene (NOI23_toxic)	C++20	38.49 / 100	5 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);
	int l = 0 , r = n-1;
	while(l < r){
		int mid = (l + r) / 2;
		vector<int>vec;
		for(int j = l;j<=mid;j++)vec.push_back(perm[j]);
		if(query_sample(vec) == mid-l+1){
			l = mid+1;
		}
		else {
			r = mid;
		}
	}
	int toxic = perm[l];
	// cout << "toxic : " << toxic << endl;
	// eliminate the strong ones
	for(int i = 0;i<n;i+=8){
		vector<int>vec;
		int bruh = 0;
		for(int j = 0;j<8;j++){
			if(i+j>=n)continue;
			int tmp = 1 << j;
			bruh += tmp;
			while(tmp--)vec.push_back(perm[i+j]);
		}
		int cevap = query_sample(vec);
		// cout << "i : " << i << endl;
		if(cevap == bruh){// S ve R lerden olusan grup
			// cout << "flag0" << endl;
			vec.push_back(toxic);
			cevap = query_sample(vec);
			for(int j = 0;j<8;j++){
				if(i+j>=n)continue;
				// cout << "answered : " << perm[i+j] << endl;
				if(cevap & (1 << j))ans[perm[i+j]] = 2;
				else ans[perm[i+j]] = 0;
			}
		}
		else{// T S R
			// cout << "flag1" << endl;
			for(int j = 0;j<8;j++){
				if(cevap & (1 << j))ans[perm[i+j]] = 2;
			}
		}
	}
	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);
	for(int i = 0;i<v.size();i+=2){
		vector<int>vec;
		if(i+2 > v.size()){
			vec.push_back(v[i]);
			if(query_sample(vec))ans[v[i]] = 0;
			else ans[v[i]] = 1;
		}
		else{
			vec.push_back(v[i]);
			vec.push_back(v[i+1]);
			int cevap = query_sample(vec);
			if(cevap == 2){
				ans[v[i]] = ans[v[i+1]] = 0;
			}
			else{
				vec.clear();
				vec.push_back(v[i]);
				if(query_sample(vec))ans[v[i]] = 0;
				else ans[v[i]] = 1;

				vec.clear();
				vec.push_back(v[i+1]);
				if(query_sample(vec))ans[v[i+1]] = 0;
				else ans[v[i+1]] = 1;
			}
		}
	}
	// cout << "n : " << n << 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: 38.4941 / 100