Submission #941044

#	Time	Username	Problem	Language	Result	Execution time	Memory
941044		daoquanglinh2007	Toxic Gene (NOI23_toxic)	C++17	8.84 / 100	9 ms	600 KiB

toxic

#include <bits/stdc++.h>
#include "toxic.h"
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 300;

int n;
char a[NM+5];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool calc(){
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] == '?') cnt++;
	return cnt;
}

void determine_type(int _n){
	int n = _n;
	for (int i = 1; i <= n; i++) a[i] = ' ';
	int l = 1, r = n, ft = -1;
	while (l <= r){
		int mid = (l+r)/2;
		vector <int> species = {};
		for (int i = 1; i <= mid; i++) species.push_back(i);
		if (query_sample(species) < mid){
			ft = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	a[ft] = 'T';
	while (true){
		vector <int> arr = {};
		for (int i = 1; i <= n; i++)
			if (a[i] == ' ' && isz(arr) < 8) arr.push_back(i);
		if (arr.empty()) break;
		vector <int> species = {};
		for (int i = 0; i < isz(arr); i++){
			for (int j = 0; j < (1<<i); j++) species.push_back(arr[i]);
		}
		species.push_back(ft);
		int tmp = query_sample(species);
		for (int i = 0; i < isz(arr); i++)
			if ((tmp>>i)&1) a[arr[i]] = 'S';
			else a[arr[i]] = '?';
	}
	while (true){
		int cnt = calc();
		if (cnt <= 30) break;
		vector <int> arr = {}, species;
		for (int i = 1; i <= n; i++)
			if (a[i] == '?') arr.push_back(i);
		shuffle(arr.begin(), arr.end(), rng);
		int sz = (cnt+29)/30;
		for (int i = 0; i < isz(arr); i += sz){
			species.clear();
			for (int j = i; j < min(i+sz, isz(arr)); j++)
				species.push_back(j);
			if (query_sample(species) > 0){
				for (int x : species) a[x] = 'R';
			}
		}	
	}
	for (int i = 1; i <= n; i++)
		if (a[i] == '?'){
			if (query_sample({i}) > 0) a[i] = 'R'; else a[i] = 'T';
		}
	for (int i = 1; i <= n; i++)
		answer_type(i, a[i]);
}

• Subtask 1: 8.83846154 / 100