제출 #1281306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281306		AMnu	Toxic Gene (NOI23_toxic)	C++20	100 / 100	6 ms	480 KiB

toxic

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

const int MAXN = 305;

int t, x;
vector <int> ord, non, g, h, c, q;
vector <vector<int>> sus;

bool tri() {
	g.clear();
	q = c;
	while (g.size() < 8 && !non.empty()) {
		g.push_back(non.back());
		non.pop_back();
	}
	for (int i=0;i<g.size();i++) {
		for (int j=0;j<(1<<i);j++) {
			q.push_back(g[i]);
		}
	}
	x = query_sample(q);
	if (x == q.size()) {
		for (int i : c) {
			answer_type(i, 'R');
		}
		for (int i : g) {
			non.push_back(i);
		}
		return 0;
	}
	for (int i=0;i<g.size();i++) {
		if ((x>>i)&1) {
			answer_type(g[i], 'S');
		}
		else {
			answer_type(g[i], 'R');
		}
	}
	return 1;
}

void two() {
	int l=0, r=h.size()-1;
	while (l<r) {
		int mid=(l+r)/2;
		q.clear();
		c.clear();
		for (int i=l;i<=mid;i++) {
			c.push_back(h[i]);
		}
		if (tri()) {
			r = mid;
		}
		else {
			l = mid+1;
		}
	}
	answer_type(h[l], 'T');
	t = h[l];
	for (int i=l+1;i<h.size();i++) {
		ord.push_back(h[i]);
	}
}

void one() {
	g.clear();
	q.clear();
	while (g.size() < 8 && !ord.empty()) {
		g.push_back(ord.back());
		ord.pop_back();
	}
	for (int i=0;i<g.size();i++) {
		for (int j=0;j<(1<<i);j++) {
			q.push_back(g[i]);
		}
	}
	x = query_sample(q);
	if (x == q.size()) {
		for (int i : g) {
			non.push_back(i);
		}
	}
	else {
		h.clear();
		for (int i=0;i<g.size();i++) {
			if ((x>>i)&1) {
				answer_type(g[i], 'S');
			}
			else {
				h.push_back(g[i]);
			}
		}
		sus.push_back(h);
	}
}

void determine_type(int n) {
	srand(time(NULL));
	for (int i=1;i<=n;i++) {
		ord.push_back(i);
		swap(ord[rand()%i],ord[i-1]);
	}
	while (!ord.empty()) {
		one();
	}
	while (!sus.empty()) {
		for (auto x : sus) {
			h = x;
			two();
		}
		sus.clear();
		while (!ord.empty()) {
			c.clear();
			while (c.size() < 8 && !ord.empty()) {
				c.push_back(ord.back());
				ord.pop_back();
			}
			if (tri()) {
				sus.push_back(c);
			}
		}
	}
	c.clear();
	c.push_back(t);
	while (!non.empty()) {
		tri();
	}
}

• Subtask 1: 100 / 100