Submission #447223

#	Time	Username	Problem	Language	Result	Execution time	Memory
447223		jwvg0425	Chameleon's Love (JOI20_chameleon)	C++17	0 / 100	1 ms	328 KiB

chameleon

#include "chameleon.h"
#include <vector>

using namespace std;

vector<int> con[1005];
bool answered[1005];
int l[1005];

int Query(int x, int s, int e)
{
	vector<int> v = { x };
	for (int i = s; i <= e; i++)
		v.push_back(i);

	return Query(v);
}

int Bisearch(int x, int l, int r, int d)
{
	int lo = l, hi = r;
	int res = 0;

	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		int q = Query(x, l, mid);
		int sz = mid - l + 2;
		if (q <= sz + d)
		{
			res = mid;
			hi = mid - 1;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return res;
}

void Solve(int N)
{
	for (int i = 1; i <= N; i++)
	{
		auto b = Bisearch(i, N + 1, 2 * N, -2);
		auto a = Bisearch(i, N + 1, b - 1, -1);
		if (Query(i, N + 1, a - 1) != a - N)
		{
			auto c = Bisearch(i, N + 1, a - 1, -1);
			con[i] = { a, b, c };
		}
		else if (Query(i, a + 1, b - 1) != b - a)
		{
			auto c = Bisearch(i, a + 1, b - 1, -1);
			con[i] = { a, b, c };
		}
		else
		{
			auto c = Bisearch(i, b + 1, 2 * N, -1);
			con[i] = { a, b, c };
		}
	}

	for (int i = N + 1; i <= 2 * N; i++)
	{
		auto b = Bisearch(i, 1, N, -2);
		auto a = Bisearch(i, 1, b - 1, -1);
		if (Query(i, 1, a - 1) != a)
		{
			auto c = Bisearch(i, 1, a - 1, -1);
			con[i] = { a, b, c };
		}
		else if (Query(i, a + 1, b - 1) != b - a)
		{
			auto c = Bisearch(i, a + 1, b - 1, -1);
			con[i] = { a, b, c };
		}
		else
		{
			auto c = Bisearch(i, b + 1, N, -1);
			con[i] = { a, b, c };
		}
	}

	for (int i = 1; i <= 2 * N; i++)
	{
		vector<int> a = { i, con[i][0], con[i][1] };
		vector<int> b = { i, con[i][0], con[i][2] };
		vector<int> c = { i, con[i][1], con[i][2] };

		auto aq = Query(a);
		auto bq = Query(b);
		auto cq = Query(c);

		if (aq == 1)
			l[i] = con[i][2];
		else if (bq == 1)
			l[i] = con[i][1];
		else
			l[i] = con[i][0];
	}

	for (int i = 1; i <= 2 * N; i++)
	{
		if (answered[i])
			continue;

		for (auto& c : con[i])
		{
			if (c == l[i] || l[c] == i || answered[c])
				continue;

			Answer(i, c);
			answered[i] = answered[c] = true;
			break;
		}
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:95:8: warning: unused variable 'cq' [-Wunused-variable]
   95 |   auto cq = Query(c);
      |        ^~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36