Submission #217529

#	Time	Username	Problem	Language	Result	Execution time	Memory
217529		Toadologist	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	69 ms	2044 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif

template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

namespace {

const int maxN = 500 * 2 + 5;
int n;
set<int> G[maxN];
vector<int> fam[maxN][2];
int pa[maxN], side[maxN];

}  // namespace

void merge(int x, int y) {
	int t = side[x] ^ side[y] ^ 1;
	fam[pa[x]][0].insert(fam[pa[x]][0].end(), fam[pa[y]][t].begin(), fam[pa[y]][t].end());
	fam[pa[x]][1].insert(fam[pa[x]][1].end(), fam[pa[y]][1^t].begin(), fam[pa[y]][1^t].end());
	int py = pa[y];
	for(int u : fam[py][0]) pa[u] = pa[x], side[u] ^= t;
	for(int u : fam[py][1]) pa[u] = pa[x], side[u] ^= t;
	fam[py][0].clear(); fam[py][1].clear();
}

void link(int x, int y) {
	eprintf("%d %d\n", x, y);
	if(pa[x] != pa[y]) merge(x, y);
	else assert(side[x] != side[y]);
	G[x].insert(y);
	G[y].insert(x);
}

void getadj(int u, vector<int> all) {
	display(u); displayv(all);
	all.insert(all.begin(), u);
	
	while(Query(all) != all.size()) {
		int L = 1, R = (int)all.size() - 1;
		while(L < R) {
			int M = (L + R) / 2;
			vector<int> q(all.begin(), all.begin() + M + 1);
			if(Query(q) != q.size()) R = M;
			else L = M + 1;
		}
		link(all[0], all[L]);
		
		all.erase(all.begin() + 1, all.begin() + L + 1);
	}
}

void Solve(int n) {
	
	::n = n;
	for(int i = 1; i <= 2 * n; ++i) {
		pa[i] = i; side[i] = 0; fam[i][0].push_back(i);
		vector<int> x, y;
		for(int j = 1; j < i; ++j) if(pa[j] == j) {
			x.insert(x.end(), fam[j][0].begin(), fam[j][0].end());
			y.insert(y.end(), fam[j][1].begin(), fam[j][1].end());
		}
		getadj(i, x);
		getadj(i, y);
	}
	int sd = 0;
	for(int i = 1; i <= 2 * n; ++i) sd += side[i];
	assert(sd == n);
	for(int i = 1; i <= 2 * n; ++i) assert(G[i].size() == 1 || G[i].size() == 3);
	
	vector<pii> rem;
	for(int i = 1; i <= 2 * n; ++i) if(G[i].size() == 3) {
		int x = *G[i].begin(), y = *next(G[i].begin()), z = *next(next(G[i].begin()));
		if(Query({i, x, y}) == 1) rem.emplace_back(i, z);
		else if(Query({i, x, z}) == 1) rem.emplace_back(i, y);
		else if(Query({i, y, z}) == 1) rem.emplace_back(i, x);
		else assert(false);
	}
	displayv(rem);
	for(auto p : rem)
		G[p.first].erase(p.second),
		G[p.second].erase(p.first);
	for(int i = 1; i <= 2 * n; ++i) {
		assert(G[i].size() == 1);
		if(*G[i].begin() > i) Answer(i, *G[i].begin());
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'void getadj(int, std::vector<int>)':
chameleon.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(Query(all) != all.size()) {
        ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(q) != q.size()) R = M;
       ~~~~~~~~~^~~~~~~~~~~

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