Submission #829726

#	Time	Username	Problem	Language	Result	Execution time	Memory
829726		rainboy	Toxic Gene (NOI23_toxic)	C++17	9.46 / 100	6 ms	388 KiB

toxic

#include "toxic.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int K = 8;

void determine_type(int n) {
	vi cc(n, '?');
	for (int i = 0; i < n; i++)
		if (query_sample({ i + 1 }) == 0)
			cc[i] = 'T';
	int t = 0;
	while (cc[t] != 'T')
		t++;
	vi ii(K); int k = 0;
	for (int i = 0; i < n; i++)
		if (cc[i] == '?') {
			ii[k++] = i;
			if (k == K) {
				vi ii_;
				ii_.push_back(t + 1);
				for (int h = 0; h < k; h++)
					for (int t = 0; t < 1 << h; t++)
						ii_.push_back(ii[h] + 1);
				int b = query_sample(ii_);
				for (int h = 0; h < k; h++)
					cc[ii[h]] = (b & 1 << h) == 0 ? 'R' : 'S';
				k = 0;
			}
		}
	if (k > 0) {
		vi ii_;
		ii_.push_back(t + 1);
		for (int h = 0; h < k; h++)
			for (int t = 0; t < 1 << h; t++)
				ii_.push_back(ii[h] + 1);
		int b = query_sample(ii_);
		for (int h = 0; h < k; h++)
			cc[ii[h]] = (b & 1 << h) == 0 ? 'R' : 'S';
		k = 0;
	}
	for (t = 0; t < n; t++)
		answer_type(t + 1, cc[t]);
}

• Subtask 1: 9.46153846 / 100