Submission #951451

#	Time	Username	Problem	Language	Result	Execution time	Memory
951451		qwe1rt1yuiop1	Toxic Gene (NOI23_toxic)	C++17	58.15 / 100	6 ms	604 KiB

toxic

#include "toxic.h"
using namespace std;
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using pii = pair<int, int>;

mt19937 rng(time(0));

vector<int> v, p, p_;
string ans;

int n0;

void ac(int x, char c)
{
	assert(ans[x] == '0');
	x = p[x];
	answer_type(x, c);
	x = p_[x];
	ans[x] = c;
}

int qry()
{
	for (int &i : v)
		i = p[i];
	int ret = query_sample(v);
	for (int &i : v)
		i = p_[i];
	return ret;
}

int qry1(int l, int r)
{
	assert(l <= r);
	v.clear();
	for (int i = l; i <= r; ++i)
		v.emplace_back(i);
	return qry();
}

void qry2()
{
	int cnt = sz(v) - 1;
	for (int i = 0; i < cnt; ++i)
		for (int j = 0; j < ((1 << i) - 1); ++j)
			v.emplace_back(v[i]);

	int tmp = sz(v);
	assert(tmp == (tmp & (-tmp)));

	int ret = qry();

	for (int i = 0; i < cnt; ++i)
		if (ret >> i & 1)
			ac(v[i], 'S');
		else
			ac(v[i], 'R');
}

vector<int> t;

void qry3(int l, int r)
{
	v.clear();
	for (int i = l, cnt = 1; i <= r; ++i, cnt *= 2)
		for (int j = 0; j < cnt; ++j)
			v.emplace_back(i);
	int ret = qry();
	if (ret == sz(v))
		return;

	int l0 = l, r0 = r;
	while (ret >> (l - l0) & 1)
		++l;
	while (ret >> (r - l0) & 1)
		--r;

	while (l <= r)
	{
		int bsl = l + 1, bsr = r + 2;
		while (bsl < bsr)
		{
			int mid = (bsl + bsr) >> 1;
			if (qry1(l, mid - 1) == mid - l)
				bsl = mid + 1;
			else
				bsr = mid;
		}
		if (bsl - 1 > r)
			break;
		t.emplace_back(bsl - 1);
		ac(bsl - 1, 'T');
		l = bsl;
	}
	for (int i = l0; i <= r0; ++i)
		if (ans[i] == '0')
		{
			if (ret >> (i - l0) & 1)
				ac(i, 'S');
			else
				ac(i, 'R');
		}
}

void determine_type(int n)
{
	p.clear();
	// p.emplace_back(0);
	for (int i = 1; i <= n; ++i)
		p.emplace_back(i);
	// p_ = p;
	shuffle(all(p), rng);
	p.emplace_back(0);
	reverse(all(p));
	p_.assign(n + 1, 0);
	for (int i = 1; i <= n; ++i)
		p_[p[i]] = i;

	n0 = n;
	ans.assign(n + 1, '0');
	t.clear();
	t.emplace_back(0);
	int nxt = 1;
	while (nxt <= n)
	{
		int l = nxt, r = min(n, l + 7);
		// qry3(l, r);
		// nxt = r + 1;
		// continue;
		if (qry1(l, r) == r - l + 1)
		{
			nxt = r + 1;
			continue;
		}
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (qry1(l, mid) != mid - l + 1)
				r = mid;
			else
				l = mid + 1;
		}
		t.emplace_back(l);
		ac(l, 'T');
		nxt = l + 1;
	}

	vector<int> r;
	for (int i = 1; i <= n; ++i)
		if (ans[i] == '0')
			r.emplace_back(i);

	while (!r.empty())
	{
		v.clear();
		while (!r.empty() && sz(v) < 8)
			v.emplace_back(r.back()), r.pop_back();
		v.emplace_back(t.back());
		qry2();
	}
}

• Subtask 1: 58.15 / 100