제출 #1272822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272822		ortsac	Toxic Gene (NOI23_toxic)	C++17	38.49 / 100	7 ms	572 KiB

toxic

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

using namespace std;

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

void determine_type(int n) {
	vector<int> tx(301);
	vector<int> ord;
	for (int i = 1; i <= n; i++) ord.push_back(i);
	shuffle(ord.begin(), ord.end(), rng);
	int qT = 0;
	for (int i = 0; i < n; i += 3) {
		vector<int> batch;
		for (int j = i; j < min(i + 3, n); j++) batch.push_back(ord[j]);
		if (query_sample(batch) != ((int) batch.size())) {
			int cnt = 0;
			for (auto u : batch) if ((cnt == 2) || (query_sample({u}) == 0)) {
				tx[u] = 1;
				qT = u;
				answer_type(u, 'T');
			} else cnt++;
		}
	}
	assert(qT != 0);
	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 = {qT};
		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: 38.4941 / 100