Submission #940900

#	Time	Username	Problem	Language	Result	Execution time	Memory
940900		TranGiaHuy1508	Toxic Gene (NOI23_toxic)	C++17	9.46 / 100	7 ms	692 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;

	int tox = 0;
	for (int i = 0; i < n; i++){
		if (!query({{i, 1}})){
			vec[i] = TOXIC;
			tox = i;
		}
		else other.push_back(i);
	}

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

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

		int mask = query(crrq);
		for (int j = 0; j < 8; 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: 9.46153846 / 100