Submission #946785

#	Time	Username	Problem	Language	Result	Execution time	Memory
946785		siewjh	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	31 ms	600 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	const int MAXN = 1005;
	vector<int> adj[MAXN];
	int clr[MAXN], ans[MAXN], dest[MAXN], found;
	
	bool query(int l, int r, int x, vector<int> &v){
		vector<int> qvec;
		for (int i = l; i <= r; i++) qvec.push_back(v[i]);
		qvec.push_back(x);
		return (Query(qvec) != qvec.size());
	}
	
	void bs(int x, vector<int> &v){
		int pos = 0, vsz = v.size();
		while (found < 3 && pos < vsz){
			if (!query(pos, vsz - 1, x, v)) return;
			int l = pos, r = vsz - 1;
			while (l < r){
				int m = (l + r) >> 1;
				if (query(l, m, x, v)) r = m;
				else l = m + 1;
			}
			adj[x].push_back(v[r]); adj[v[r]].push_back(x);
			found++;
			pos = r + 1;
		}
	}
	
	void dfs(int x, int c){
		clr[x] = c;
		for (int nxt : adj[x])
			if (clr[nxt] == -1)
				dfs(nxt, 1 - c);
	}
}  // namespace

void Solve(int N) {
	vector<int> grps[2];
	for (int i = 1; i <= 2 * N; i++){
		found = 0;
		bs(i, grps[0]); bs(i, grps[1]);
		memset(clr, -1, sizeof(clr));
		for (int j = 1; j <= i; j++)
			if (clr[j] == -1)
				dfs(j, 0);
		grps[0].clear(); grps[1].clear();
		for (int j = 1; j <= i; j++) grps[clr[j]].push_back(j);
	}
	memset(dest, -1, sizeof(dest));
	for (int i = 1; i <= 2 * N; i++){
		if (adj[i].size() == 1) ans[i] = adj[i][0];
		else{
			for (int k = 0; k <= 2; k++){
				vector<int> qvec; qvec.push_back(i);
				for (int ind = 0; ind <= 2; ind++)
					if (ind != k)
						qvec.push_back(adj[i][ind]);
				if (Query(qvec) == 1){
					dest[i] = adj[i][k];
					break;
				}
			}
		}
	}
	for (int i = 1; i <= 2 * N; i++){
		if (adj[i].size() == 1) continue;
		for (int k = 0; k <= 2; k++)
			if (adj[i][k] != dest[i] && dest[adj[i][k]] != i){
				ans[i] = adj[i][k];
				break;
			}
	}
	for (int i = 1; i <= 2 * N; i++)
		if (ans[i] > i)
			Answer(i, ans[i]);
}

Compilation message (stderr)

chameleon.cpp: In function 'bool {anonymous}::query(int, int, int, std::vector<int>&)':
chameleon.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   return (Query(qvec) != qvec.size());
      |           ~~~~~~~~~~~~^~~~~~~~~~~~~~

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