Submission #670675

#	Time	Username	Problem	Language	Result	Execution time	Memory
670675		rainboy	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	38 ms	380 KiB

chameleon

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

namespace C {
	const int N = 500;
	int ii[4][N * 2], cnt[4];
	int ej[N * 2 + 1][3], eo[N * 2 + 1];
	int mate[N * 2 + 1];
	void append(int i, int j) {
		ej[i][eo[i]++] = j, ej[j][eo[j]++] = i;
	}
}

void Solve(int n) {
	for (int i = 1; i <= n * 2; i++)
		for (int c = 0; c < 4; c++) {
			C::ii[c][C::cnt[c]++] = i;
			if (c == 3 || Query(vector(C::ii[c], C::ii[c] + C::cnt[c])) == C::cnt[c])
				break;
			C::cnt[c]--;
		}
	for (int a = 0; a < 4; a++)
		for (int h = 0; h < C::cnt[a]; h++) {
			int i = C::ii[a][h];
			for (int b = a + 1; b < 4; b++) {
				int l = 0;
				while (l < C::cnt[b]) {
					vi v = vector(C::ii[b] + l, C::ii[b] + C::cnt[b]); v.push_back(i);
					if (Query(v) < C::cnt[b] - l + 1) {
						int lower = l, upper = C::cnt[b];
						while (upper - lower > 1) {
							int r = (lower + upper) / 2;
							v = vector(C::ii[b] + l, C::ii[b] + r); v.push_back(i);
							if (Query(v) < r - l + 1)
								upper = r;
							else
								lower = r;
						}
						C::append(i, C::ii[b][lower]);
						l = upper;
					} else
						break;
				}
			}
		}
	for (int i = 1; i <= n * 2; i++)
		if (C::eo[i] == 1)
			C::mate[i] = C::ej[i][0];
		else {
			int tmp;
			if (Query(vector({i, C::ej[i][0], C::ej[i][2]})) == 1)
				tmp = C::ej[i][0], C::ej[i][0] = C::ej[i][1], C::ej[i][1] = tmp;
			else if (Query(vector({i, C::ej[i][0], C::ej[i][1]})) == 1)
				tmp = C::ej[i][0], C::ej[i][0] = C::ej[i][2], C::ej[i][2] = tmp;
		}
	for (int i = 1; i <= n * 2; i++)
		if (C::eo[i] > 1) {
			int j = C::ej[i][1], k = C::ej[i][2];
			C::mate[i] = C::eo[j] == 1 || C::ej[j][0] != i ? j : k;
		}
	for (int i = 1; i <= n * 2; i++)
		if (i < C::mate[i])
			Answer(i, C::mate[i]);
}

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