Submission #223094

#	Time	Username	Problem	Language	Result	Execution time	Memory
223094		Andrei_Cotor	Chameleon's Love (JOI20_chameleon)	C++14	64 / 100	65 ms	508 KiB

chameleon

//o pereche de 2 cameleoni (x,y) va da rasp 1 daca: color(x)=color(y), x il iubeste pe y, y il iubeste pe x
//impart in 4 seturi a.i. cameleonii din cele 4 seturi sunt independenti
#include"chameleon.h"
#include<vector>

using namespace std;

vector<int> Sets[4];
vector<int> Adj[1005];
bool Answered[1005];
int Loves[1005],Loved[1005]; //loves=pe cine, loved=de cine

int getCandidate(int cham, int s, int dec)
{
	vector<int> Aux;
	int poz=dec-1;
	for(int i=9; i>=0; i--)
	{
		if(poz+(1<<i)<Sets[s].size())
		{
			Aux.clear();
			Aux.push_back(cham);
			for(int j=dec; j<=poz+(1<<i); j++)
				Aux.push_back(Sets[s][j]);

			if(Query(Aux)==Aux.size())
				poz+=(1<<i);
		}
	}
	poz++;
	return poz;
}

void Solve(int n)
{
	for(int i=1; i<=2*n; i++)
	{
		for(int j=0; j<4; j++)
		{
			Sets[j].push_back(i);

			if(Query(Sets[j])==Sets[j].size())
				break;

			Sets[j].pop_back();
		}
	}

	for(int i=0; i<4; i++)
	{
		for(auto cham:Sets[i])
		{
			for(int j=i+1; j<4; j++)
			{
				int lastcand=-1;
				while(1)
				{
					int cand=getCandidate(cham,j,lastcand+1);

					if(cand==Sets[j].size())
						break;

					Adj[cham].push_back(Sets[j][cand]);
					Adj[Sets[j][cand]].push_back(cham);
					lastcand=cand;
				}
			}
		}
	}

	for(int i=1; i<=2*n; i++)
	{
		if(Answered[i])
			continue;

		if(Adj[i].size()==1) //i iubeste si este iubit de acelasi cameleon, deci cel din Adj este cel de aceasi culoare
		{
			Answer(i,Adj[i][0]);
			Answered[i]=1;
			Answered[Adj[i][0]]=1;
		}
	}

	vector<int> Aux;
	for(int i=1; i<=2*n; i++)
	{
		if(Adj[i].size()==1)
			continue;

		Aux.clear();
		Aux.push_back(i);
		Aux.push_back(Adj[i][0]);
		Aux.push_back(Adj[i][1]);

		if(Query(Aux)==1)
		{
			Loves[i]=Adj[i][2];
			Loved[Adj[i][2]]=i;
			continue;
		}

		Aux[2]=Adj[i][2];
		if(Query(Aux)==1)
		{
			Loves[i]=Adj[i][1];
			Loved[Adj[i][1]]=i;
			continue;
		}

		Aux[1]=Adj[i][1];
		if(Query(Aux)==1)
		{
			Loves[i]=Adj[i][0];
			Loved[Adj[i][0]]=i;
			continue;
		}
	}

	for(int i=1; i<=2*n; i++)
	{
		if(Answered[i])
			continue;

		int per=Adj[i][0]^Adj[i][1]^Adj[i][2]^Loves[i]^Loved[i];
		Answer(i,per);
		Answered[per]=1;
		Answered[i]=1;
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'int getCandidate(int, int, int)':
chameleon.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(poz+(1<<i)<Sets[s].size())
      ~~~~~~~~~~^~~~~~~~~~~~~~~
chameleon.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(Aux)==Aux.size())
       ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(Sets[j])==Sets[j].size())
       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
chameleon.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(cand==Sets[j].size())
         ~~~~^~~~~~~~~~~~~~~~

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