Submission #1272807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272807		ortsac	Toxic Gene (NOI23_toxic)	C++20	28.40 / 100	9 ms	576 KiB

toxic

#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

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

int cnt = 0;

vector<int> gRange(int l, int r) {
	vector<int> a;
	for (int i = l; i <= r; i++) a.push_back(i);
	return a;
}

bool good(int l, int r) {
	return (query_sample(gRange(l, r)) == (r - l + 1));
}

vector<int> toxics;

void doIt(int l, int r) {
	if (l == r) {
		toxics.push_back(l);
		return;
	}
	int m = (l + r)/2;
	vector<pii> ra = {{l, m}, {m + 1, r}};
	shuffle(ra.begin(), ra.end(), rng);
	cnt++;
	if (good(ra[0].fr, ra[0].se)) {
		doIt(ra[1].fr, ra[1].se);
		// ok
	} else {
		cnt++;
		doIt(ra[0].fr, ra[0].se);
		if (!good(ra[1].fr, ra[1].se)) doIt(ra[1].fr, ra[1].se);;
	}
}

void determine_type(int n) {
	cnt = 0;
	toxics.clear();
	doIt(1, n);
	vector<int> tx(301);
	for (auto u : toxics) {
		tx[u] = 1;
		answer_type(u, 'T');
	}
	vector<int> test;
	for (int i = 1; i <= n; i++) {
		if (!tx[i]) test.push_back(i);
	}
	while (!test.empty()) {
		vector<int> curr;
		while (!test.empty() && (((int) curr.size()) < 8)) {
			curr.push_back(test.back());
			test.pop_back();
		}
		vector<int> batch = {toxics[0]};
		for (int i = 0; i < ((int) curr.size()); i++) {
			int qtd = (1 << i);
			while (qtd--) batch.push_back(curr[i]);
		}
		int r = query_sample(batch);
		for (int i = 0; i < ((int) curr.size()); i++) {
			if (r & (1 << i)) {
				answer_type(curr[i], 'S');
			} else {
				answer_type(curr[i], 'R');
			}
		}
	}
	return;
}

• Subtask 1: 28.4 / 100