Submission #464241

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

chameleon

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

using namespace std;

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

void f(int b, int x, int s, int e) {
	if (s==e) {
		vector<int> v(2);
		v[0]=x, v[1]=bi[b][s];
		if (bi[b].size()!=1&&Query(v)!=1) return ;
		adj[x].emplace_back(bi[b][s]);
		adj[bi[b][s]].emplace_back(x);
		return ;
	}
	vector<int> v(1, x), w(1, x);
	int m=(s+e)/2;
	for (int i=s; i<=m; i++) v.emplace_back(bi[b][i]);
	if (Query(v)<v.size()) f(b, x, s, m);
	for (int i=m+1; i<=e; i++) w.emplace_back(bi[b][i]);
	if (Query(w)<w.size()) f(b, x, m+1, e);
}

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++) {
		for (int j=0; j<2; j++) if (bi[j].size()) f(j, i, 0, bi[j].size()-1);
		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;
	};
	for (int i=1; i<=n; i++) for (auto &j:adj[i]) if (i<j&&chk(i, j)) {
		Answer(i, j);
		adj[j].clear();
		break;
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'void f(int, int, int, int)':
chameleon.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  if (Query(v)<v.size()) f(b, x, s, m);
      |      ~~~~~~~~^~~~~~~~~
chameleon.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  if (Query(w)<w.size()) f(b, x, m+1, e);
      |      ~~~~~~~~^~~~~~~~~

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