Submission #941049

#	Time	Username	Problem	Language	Result	Execution time	Memory
941049		daoquanglinh2007	Toxic Gene (NOI23_toxic)	C++17	9.46 / 100	7 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] = '?';
	while (true){
		int cnt = calc();
		if (cnt <= 60) 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) == isz(species)){
				for (int x : species) a[x] = '!';
			}
		}	
	}
	int ft = -1;
	for (int i = 1; i <= n; i++)
		if (a[i] == '?'){
			if (query_sample({i}) > 0) a[i] = '!'; else a[i] = 'T';
			if (ft == -1 && a[i] == 'T') ft = i;
		}
	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]] = 'R';
	}
	for (int i = 1; i <= n; i++)
		answer_type(i, a[i]);
}

• Subtask 1: 9.46153846 / 100