Submission #464272

#	Time	Username	Problem	Language	Result	Execution time	Memory
464272		koioi.org-dennisstar	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	80 ms	484 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int> bi[2];

bool f(int b, int x) {
	vector<int> v(1, x);
	for (auto &i:bi[b]) v.emplace_back(i);
	if (Query(v)==v.size()) return false;
	
	int s=0, e=bi[b].size()-1;
	while (s<e) {
		int m=(s+e)/2;
		vector<int> w(1, x);
		for (int j=0; j<=m; j++) w.emplace_back(bi[b][j]);
		if (Query(w)==w.size()) s=m+1;
		else e=m;
	}
	adj[x].emplace_back(bi[b][s]);
	adj[bi[b][s]].emplace_back(x);
	for (int i=s+1; i<bi[b].size(); i++) bi[b][i-s-1]=bi[b][i];
	bi[b].resize(bi[b].size()-s-1);

	return true;
}

vector<int> vis; int vc;

void dfs(int i, int b) {
	vis[i]=vc;
	bi[b].emplace_back(i);
	for (auto &j:adj[i]) if (vis[j]!=vc) dfs(j, 1-b);
}

void div(int n) {
	bi[0].clear();
	bi[1].clear();
	vc++;
	for (int i=1; i<=n; i++) if (vis[i]!=vc) dfs(i, 0);
}

void Solve(int n) {
	n*=2;
	adj.resize(n+1);
	vis.resize(n+1);
	for (int i=1; i<=n; i++) {
		while (f(0, i));
		while (f(1, i));
		div(i);
	}

	auto chk = [&](int x, int y) {
		if (adj[x].size()==1||adj[y].size()==1) return true;
		int f1=0, f2=0;
		vector<int> v(3);
		v[0]=x, v[1]=y;
		for (auto &i:adj[x]) if (i!=y) {
			v[2]=i;
			if (Query(v)==1) { f1=1; break; }
		}
		for (auto &i:adj[y]) if (i!=x) {
			v[2]=i;
			if (Query(v)==1) { f2=1; break; }
		}
		return f1&&f2;
	};
	vector<int> used(n+1);
	for (int i=1; i<=n; i++) if (!used[i]) for (auto &j:adj[i]) if (!used[j]&&i<j&&chk(i, j)) {
		used[i]=used[j]=1;
		Answer(i, j);
		adj[j].clear();
		break;
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'bool f(int, int)':
chameleon.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  if (Query(v)==v.size()) return false;
      |      ~~~~~~~~^~~~~~~~~~
chameleon.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   if (Query(w)==w.size()) s=m+1;
      |       ~~~~~~~~^~~~~~~~~~
chameleon.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i=s+1; i<bi[b].size(); i++) bi[b][i-s-1]=bi[b][i];
      |                  ~^~~~~~~~~~~~~

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