Submission #444243

#	Time	Username	Problem	Language	Result	Execution time	Memory
444243		kig9981	Chameleon's Love (JOI20_chameleon)	C++17	0 / 100	1 ms	328 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;

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 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);
		for(int l=-1;l<V[0].size();) {
			int s=l+1, e=V[0].size()-1;
			while(s<=e) {
				int m=(s+e)>>1;
				Q.clear(); Q.push_back(i);
				for(int k=l+1;k<=m;k++) Q.push_back(V[0][k]);
				if(Query(Q)==Q.size()) s=m+1;
				else e=m-1;
			}
			if(s==V[0].size()) break;
			adj[V[0][s]].push_back(i);
			adj[i].push_back(V[0][s]);
			l=s;
		}
		for(int l=-1;l<V[1].size();) {
			int s=l+1, e=V[1].size()-1;
			while(s<=e) {
				int m=(s+e)>>1;
				Q.clear(); Q.push_back(i);
				for(int k=l+1;k<=m;k++) Q.push_back(V[1][k]);
				if(Query(Q)==Q.size()) s=m+1;
				else e=m-1;
			}
			if(s==V[1].size()) break;
			adj[V[1][s]].push_back(i);
			adj[i].push_back(V[1][s]);
			l=s;
		}
	}
	memset(chk,0,sizeof(chk));
	for(int i=1;i<=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(k);
			if(Query(Q)==1) {
				P[i]=adj[i][j];
				break;
			}
		}
		E[i].push_back(P[i]);
		E[P[i]].push_back(i);
	}
	for(int i=1;i<=N;i++) if(!chk[i]) {
		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 Solve(int)':
chameleon.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int l=-1;l<V[0].size();) {
      |                ~^~~~~~~~~~~~
chameleon.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(Query(Q)==Q.size()) s=m+1;
      |        ~~~~~~~~^~~~~~~~~~
chameleon.cpp:40:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    if(s==V[0].size()) break;
      |       ~^~~~~~~~~~~~~
chameleon.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int l=-1;l<V[1].size();) {
      |                ~^~~~~~~~~~~~
chameleon.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if(Query(Q)==Q.size()) s=m+1;
      |        ~~~~~~~~^~~~~~~~~~
chameleon.cpp:54:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if(s==V[1].size()) break;
      |       ~^~~~~~~~~~~~~

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