Submission #330291

#	Time	Username	Problem	Language	Result	Execution time	Memory
330291		maximath_1	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	67 ms	644 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

bool bad(vector<int> v, int x){
	v.push_back(x);
	return Query(v) != v.size();
}

void Solve(int n){
	vector<int> adj[2 * n + 5];

	for(int cr = 1; cr <= 2 * n; cr ++){
		vector<int> color(cr), inset[2];

		function<void(int, int)> dfs = [&](int nw, int cl){
			if(color[nw]) return;
			color[nw] = cl;
			for(int nx : adj[nw])
				dfs(nx, 3 - cl);
		};

		for(int i = 1; i < cr; i ++){
			if(!color[i]) dfs(i, 1);
			inset[color[i] - 1].push_back(i);
		}

		for(int i = 0; i < 2; i ++){
			while(bad(inset[i], cr)){
				int lf = 1, rg = inset[i].size();
				for(int md; lf < rg;){
					md = (lf + rg) / 2;
					if(bad(vector<int>(inset[i].begin(), inset[i].begin() + md), cr))
						rg = md;
					else
						lf = md + 1;
				}

				adj[cr].push_back(inset[i][lf - 1]);
				adj[inset[i][lf - 1]].push_back(cr);

				inset[i] = vector<int>(inset[i].begin() + lf, inset[i].end());
			}
		}
	}

	vector<int> same(2 * n + 5), n1(2 * n + 5), n2(2 * n + 5);

	for(int i = 1; i <= 2 * n; i ++){
		if(adj[i].size() == 1)
			same[i] = adj[i][0];
		else{
			while(Query({i, adj[i][0], adj[i][1]}) != 1)
				rotate(adj[i].begin(), adj[i].begin() + 1, adj[i].end());
			n1[i] = adj[i][2];
			n2[adj[i][2]] = i;
		}
	}

	for(int i = 1; i <= 2 * n; i ++){
		if(!same[i])
			same[i] = adj[i][0] + adj[i][1] + adj[i][2] - n1[i] - n2[i];
		if(i > same[i])
			Answer(same[i], i);
	}

	return;
}

Compilation message (stderr)

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

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