Submission #940937

#	Time	Username	Problem	Language	Result	Execution time	Memory
940937		TranGiaHuy1508	Toxic Gene (NOI23_toxic)	C++17	100 / 100	25 ms	600 KiB

toxic

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

#include "toxic.h"

enum BacteriaType {
	REGULAR = 'R',
	 STRONG = 'S',
	  TOXIC = 'T'
};

int query(vector<pair<int, int>> samples){
	vector<int> species;
	for (auto [type, cnt]: samples){
		for (int _ = 0; _ < cnt; _++) species.push_back(type + 1);
	}
	return query_sample(species);
}

void determine_type(int n){
	vector<char> vec(n, REGULAR);
	vector<int> other;

	static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

	vector<int> lst(n);
	iota(lst.begin(), lst.end(), 0);

	vector<int> bruh;
	int tox = 0;

	int toxic_count = 0;

	while (!lst.empty()){
		shuffle(lst.begin(), lst.end(), rng);

		vector<pair<int, int>> crrq;
		int a = 1;

		while (!lst.empty() && a < 256){
			crrq.emplace_back(lst.back(), a);
			a <<= 1;
			lst.pop_back();
		}

		int mask = query(crrq);
		vector<int> dead;

		if (mask == (1 << crrq.size()) - 1){
			for (auto elem: crrq) bruh.push_back(elem.first);
			continue;
		}
		else{
			for (int j = 0; j < (int)crrq.size(); j++){
				if ((mask >> j) & 1) vec[crrq[j].first] = STRONG;
				else dead.push_back(crrq[j].first);
			}
		}

		int l = 0, r = dead.size() - 1;
		while (l < r){
			int mid = (l + r) >> 1;

			vector<pair<int, int>> subq;

			// We try to consume stuff from <bruh>
			int a = 1, k = 0;
			while (!bruh.empty() && a < 256){
				subq.emplace_back(bruh.back(), a);
				a <<= 1; k++;
				bruh.pop_back();
			}

			for (int j = 0; j <= mid; j++) subq.emplace_back(dead[j], 1);

			int mask = query(subq);
			if (mask == mid+1 + (1 << k) - 1){
				l = mid + 1;
				for (int j = 0; j < k; j++) bruh.push_back(subq[j].first);
			}
			else{
				r = mid;
				for (int j = 0; j < k; j++){
					if ((mask >> j) & 1) vec[subq[j].first] = STRONG;
				}
			}
		}

		vec[dead[l]] = TOXIC; tox = dead[l];
		for (int j = l+1; j < (int)dead.size(); j++) lst.push_back(dead[j]);
		toxic_count++;
		if (toxic_count == 30){
			bruh.insert(bruh.end(), lst.begin(), lst.end());
			lst.clear();
		}
	}

	while (!bruh.empty()){
		vector<pair<int, int>> crrq;
		int a = 1;

		while (!bruh.empty() && a < 256){
			crrq.emplace_back(bruh.back(), a);
			a <<= 1;
			bruh.pop_back();
		}
		crrq.emplace_back(tox, 1);

		int mask = query(crrq);
		for (int j = 0; j < (int)crrq.size() - 1; j++){
			if ((mask >> j) & 1) vec[crrq[j].first] = STRONG;
		}
	}

	for (int i = 0; i < n; i++) answer_type(i+1, vec[i]);
}

• Subtask 1: 100 / 100