Submission #444252

#	Time	Username	Problem	Language	Result	Execution time	Memory
444252		kig9981	Chameleon's Love (JOI20_chameleon)	C++17	4 / 100	86 ms	760 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
int Query(const std::vector<int> &p);
void Answer(int a, int b);
 
vector<int> adj[1001], V[2], Q, E[1001];
int P[1001];
bool chk[1001];
 
void dfs(int c, int v)
{
	V[v].push_back(c);
	chk[c]=true;
	for(auto n: adj[c]) if(!chk[n]) dfs(n,v^1);
}
 
void check(int v, int l, int r, int i)
{
	if(l>r || adj[i].size()==3) return;
	int s=l, e=r;
	while(s<=e) {
		int m=(s+e)>>1;
		Q.clear(); Q.push_back(i);
		for(int k=l;k<=m;k++) Q.push_back(V[v][k]);
		if(Query(Q)==Q.size()) s=m+1;
		else e=m-1;
	}
	if(s>r) return;
	adj[V[v][s]].push_back(i);
	adj[i].push_back(V[v][s]);
	check(v,s+1,r,i);
}
 
void Solve(int N)
{
	for(int i=1;i<=2*N;i++) {
		V[0].clear(); V[1].clear();
		for(int j=1;j<i;j++) chk[j]=false;
		for(int j=1;j<i;j++) if(!chk[j]) dfs(j,0);
		check(0,0,V[0].size()-1,i);
		check(1,0,V[1].size()-1,i);
	}
	memset(chk,0,sizeof(chk));
	for(int i=1;i<=2*N;i++) if(!chk[i]) {
		if(adj[i].size()==1) {
			Answer(i,adj[i][0]);
			chk[i]=chk[adj[i][0]]=true;
			continue;
		}
		for(int j=0;j<3;j++) {
			Q.clear(); Q.push_back(i);
			for(int k=0;k<3;k++) if(k^j) Q.push_back(adj[i][k]);
			if(Query(Q)==1) {
				P[i]=adj[i][j];
				break;
			}
		}
		assert(P[i]);
		E[i].push_back(P[i]);
		E[P[i]].push_back(i);
	}
	for(int i=1;i<=2*N;i++) if(!chk[i]) {assert(E[i].size()==2);
		for(auto a: adj[i]) {
			bool valid=true;
			for(auto b: E[i]) if(a==b) valid=false;
			if(valid) {
				Answer(i,a);
				chk[i]=chk[a]=true;
				break;
			}
		}
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'void check(int, int, int, int)':
chameleon.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(Query(Q)==Q.size()) s=m+1;
      |      ~~~~~~~~^~~~~~~~~~

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