Submission #950994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
950994	2024-03-21T03:47:57 Z	qwe1rt1yuiop1	Toxic Gene (NOI23_toxic)	C++17	25.2941 / 100	11 ms	536 KB

toxic

#include "toxic.h"
using namespace std;
#include <bits/stdc++.h>
#define sz(x) (int)x.size()

mt19937 rng(48763);

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 cnt1 = 0, cnt2 = 0;

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

void qry2()
{
	++cnt2;
	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();
	// --ret;

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

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

	cnt1 = cnt2 = 0;
	n0 = n;
	ans.assign(n + 1, '0');
	vector<int> t;
	t.emplace_back(0);
	while (1)
	{
		int l = t.back() + 2, r = n + 2;
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (qry1(t.back() + 1, mid - 1) == (mid - 1) - (t.back() + 1) + 1)
				l = mid + 1;
			else
				r = mid;
		}
		if (l - 1 > n)
			break;
		t.emplace_back(l - 1);
		ac(l - 1, 'T');
		/*
			int l = t.back() + 1, r = n;
			if (l > r || qry1(l, r) == r - l + 1)
				break;
			while (l < r)
			{
				int mid = (l + r) >> 1;
				if (qry1(l, mid) == mid - l + 1)
					l = mid + 1;
				else
					r = mid;
			}
			t.emplace_back(l);
			ac(l, 'T');
		*/
	}

	/*
		for (int i = 1; i <= n; ++i)
			if (ans[i] == '0')
			{
				v.clear();
				v.emplace_back(t.back());
				v.emplace_back(i);
				if (qry() == 1)
					ac(i, 'S');
				else
					ac(i, 'R');
			}
	*/

	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();
	}
	assert(cnt2 <= 40);
	assert(cnt1 <= 280);
}

Subtask #1

25.29411765 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Partially correct	7 ms	348 KB	Partially correct
3	Partially correct	7 ms	348 KB	Partially correct
4	Partially correct	8 ms	348 KB	Partially correct
5	Partially correct	8 ms	348 KB	Partially correct
6	Partially correct	8 ms	516 KB	Partially correct
7	Partially correct	8 ms	348 KB	Partially correct
8	Partially correct	8 ms	348 KB	Partially correct
9	Partially correct	11 ms	520 KB	Partially correct
10	Partially correct	9 ms	348 KB	Partially correct
11	Partially correct	9 ms	524 KB	Partially correct
12	Partially correct	7 ms	348 KB	Partially correct
13	Partially correct	8 ms	348 KB	Partially correct
14	Partially correct	8 ms	536 KB	Partially correct
15	Partially correct	9 ms	348 KB	Partially correct
16	Partially correct	8 ms	520 KB	Partially correct
17	Partially correct	8 ms	348 KB	Partially correct
18	Partially correct	8 ms	348 KB	Partially correct
19	Partially correct	9 ms	344 KB	Partially correct
20	Partially correct	10 ms	348 KB	Partially correct
21	Partially correct	9 ms	348 KB	Partially correct
22	Partially correct	10 ms	348 KB	Partially correct
23	Partially correct	7 ms	348 KB	Partially correct
24	Partially correct	7 ms	348 KB	Partially correct
25	Partially correct	7 ms	348 KB	Partially correct
26	Partially correct	7 ms	348 KB	Partially correct
27	Partially correct	7 ms	348 KB	Partially correct
28	Partially correct	9 ms	348 KB	Partially correct
29	Partially correct	8 ms	520 KB	Partially correct
30	Partially correct	8 ms	348 KB	Partially correct
31	Partially correct	8 ms	520 KB	Partially correct
32	Partially correct	9 ms	348 KB	Partially correct
33	Partially correct	9 ms	516 KB	Partially correct
34	Partially correct	8 ms	348 KB	Partially correct
35	Partially correct	8 ms	348 KB	Partially correct
36	Partially correct	1 ms	348 KB	Partially correct