Submission #219436

#	Time	Username	Problem	Language	Result	Execution time	Memory
219436		atoiz	카멜레온의 사랑 (JOI20_chameleon)	C++14	100 / 100	106 ms	512 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <array>
#include <iostream>

using namespace std;

void Solve(int N)
{
	N *= 2;

	vector<vector<int>> groups;
	vector<vector<int>> adj(N + 1);
	vector<int> to(N + 1, 0);
	vector<int> same(N + 1, 0);

	auto ask = [&](vector<int> vec, int x) -> bool {
		vec.push_back(x);
		return Query(vec) == (int) vec.size();
	};

	auto find_neighbor = [&](vector<int> vec, int x) -> int {
		if (ask(vec, x)) return 0;
		while ((int) vec.size() > 1) {
			int mid = (int) vec.size() / 2;
			if (ask(vector<int>(vec.begin(), vec.begin() + mid), x)) {
				vec.erase(vec.begin(), vec.begin() + mid);
			} else {
				vec.erase(vec.begin() + mid, vec.end());
			}
		}
		return vec[0];
	};

	for (int x = 1; x <= N; ++x) {
		int id = -1;
		for (int g_id = 0; g_id < (int) groups.size(); ++g_id) {
			vector<int> cur = groups[g_id];
			int y = 0;
			bool in_group = true;

			while ((y = find_neighbor(cur, x))) {
				adj[x].push_back(y);
				adj[y].push_back(x);
				in_group = false;
				cur.erase(find(cur.begin(), cur.end(), y));
			}

			if (in_group) id = g_id;
		}

		if (!~id) { groups.push_back(vector<int>{x}); }
		else groups[id].push_back(x);
	}
	assert((int) groups.size() <= 4);

	for (int x = 1; x <= N; ++x) {
		if ((int) adj[x].size() == 1) {
			if (!same[x]) {
				same[x] = adj[x][0];
				same[adj[x][0]] = x;
			}
		} else {
			assert((int) adj[x].size() == 3);
			to[x] = adj[x][0];
			for (int k = 1; k <= 2; ++k) {
				vector<int> vec = adj[x];
				vec.erase(vec.begin() + k);
				vec.push_back(x);
				if (Query(vec) == 1) {
					to[x] = adj[x][k];
					break;
				}
			}

			for (int p = x, u = to[x]; u != x; p = u, u = to[u]) { // find to[u], same[u]
				assert((int) adj[u].size() == 3);

				vector<int> candidates;
				for (int i : adj[u]) {
					if (i != same[u] && i != p) candidates.push_back(i);
				}

				if ((int) candidates.size() == 1) {
					assert(same[u]);
					to[u] = candidates[0];
				} else {
					assert(!same[u]);
					assert((int) candidates.size() == 2);
					if (Query(vector<int> {candidates[0], p, u}) == 1) {
						same[u] = candidates[0], to[u] = candidates[1];
					} else {
						same[u] = candidates[1], to[u] = candidates[0];
					}
				}
			}

			if (!same[x]) {
				for (int i : adj[x]) {
					if (i != to[x] && to[i] != x) assert(!same[x]), same[x] = i;
				}
				assert(same[x]);
			}
		}
	}

	for (int x = 1; x <= N; ++x) {
		assert(same[x]);
		if (x < same[x]) Answer(x, same[x]);
	}
}

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