Submission #223109

#	Time	Username	Problem	Language	Result	Execution time	Memory
223109		Andrei_Cotor	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	54 ms	512 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>
#include<iostream>

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
bool Viz[1005];
int nrq;

bool check(int cham, int s, int st, int dr)
{
	if(st>dr)
		return 0;

	vector<int> Aux;
	Aux.push_back(cham);
	for(int j=st; j<=dr; j++)
		Aux.push_back(Sets[s][j]);

	nrq++;
	if(Query(Aux)==Aux.size())
		return 0;
	return 1;
}

int getCandidate(int cham, int s, int dec)
{
	int poz=dec-1;
	for(int i=9; i>=0; i--)
	{
		if(poz+(1<<i)<Sets[s].size() && !check(cham,s,dec,poz+(1<<i)))
			poz+=(1<<i);
	}
	poz++;
	return poz;
}

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

			if(Query(Sets[j])==Sets[j].size())
			{
				if(ind==-1 || Sets[j].size()<Sets[ind].size()) //le echilibrez cat mai mult pt a optimiza nr de pasi de la cautare
					ind=j;
			}

			Sets[j].pop_back();
		}

		Sets[ind].push_back(i);
	}

	for(int i=0; i<4; i++)
	{
		for(auto cham:Sets[i])
		{
			int nr=0;
			for(int j=i+1; j<4; j++)
			{
				int lastcand=-1;
				while(nr<3)
				{
					if(!check(cham,j,lastcand+1,Sets[j].size()-1))
						break;

					int cand=getCandidate(cham,j,lastcand+1);

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

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

				if(nr==3)
					break;
			}
		}
	}
	//cout<<nrq<<"\n";

	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 ind=1; ind<=2*n; ind++)
	{
		int i=ind;
		while(!Viz[i])
		{
			Viz[i]=1;
			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(Loved[i]!=Adj[i][2] && Query(Aux)==1)
			{
				Loves[i]=Adj[i][2];
				Loved[Adj[i][2]]=i;

				i=Loves[i];
				continue;
			}

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

				i=Loves[i];
				continue;
			}

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

				i=Loves[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 'bool check(int, int, int, int)':
chameleon.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(Query(Aux)==Aux.size())
     ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'int getCandidate(int, int, int)':
chameleon.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(poz+(1<<i)<Sets[s].size() && !check(cham,s,dec,poz+(1<<i)))
      ~~~~~~~~~~^~~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(Sets[j])==Sets[j].size())
       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
chameleon.cpp:80: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: 36 / 36