Submission #164455

#	Time	Username	Problem	Language	Result	Execution time	Memory
164455		Lawliet	ICC (CEOI16_icc)	C++14	0 / 100	8 ms	888 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;//INCLUIR BIBLIO
 
const int MAXN = 110;
 
int N;
 
int pai[MAXN];
int aux[MAXN];
int white[MAXN];
int vLeft[MAXN];
int vRight[MAXN];
 
bool marc[MAXN];
 
vector< int > Left;
vector< int > Right;
vector< int > curNodes;
 
vector< int > nodes[MAXN];
vector< int > black[MAXN];
 
/*int query(int sa, int sb, int* a, int* b)
{
	printf("\n-> ");
	for(int i = 0 ; i < sa ; i++)
		printf("%d ",a[i]);
 
	printf("\n-> ");
	for(int i = 0 ; i < sb ; i++)
		printf("%d ",b[i]);
 
	printf("\n");
	int l;
	scanf("%d",&l);
 
	return l;
}*/
 
int find(int i)
{
	if( pai[i] == i ) return i;
	return pai[i] = find( pai[i] );
}
 
void join(int i, int j)
{
	i = find( i );
	j = find( j );
 
	if( i == j ) return;
 
	if( nodes[i].size() < nodes[j].size() ) swap( i , j );
 
	pai[ j ] = i;
	
	while( !nodes[j].empty() )
	{
		nodes[ i ].push_back( nodes[j].back() );
		nodes[ j ].pop_back();
	}
}
 
int bsComponent()
{
	for(int i = 0 ; i < Left.size() ; i++)
		vLeft[ i ] = Left[ i ];
 
	int L = 0;
	int R = Right.size() - 1;
 
	while( L < R )
	{
		int m = ( L + R )/2;
 
		for(int i = L ; i <= m ; i++)
			vRight[ i - L ] = Right[ i ];
 
		if( query( Left.size() , m - L + 1 , vLeft , vRight ) == 1 ) R = m;
		else L = m + 1;
	}
 
	return Right[ L ];
}
 
void bsPieces()
{
	int sz = curNodes.size();
 
	while( true )
	{
		int m = sz/2;
 
		int curL = 0;
		int curR = 0;
 
		for(int i = 0 ; i < curNodes.size() ; i++)
		{
			if( i%sz < m ) 
			{
				for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
					vLeft[ curL++ ] = nodes[ curNodes[i] ][ j ];
			}
			else 
			{
				for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
					vRight[ curR++ ] = nodes[ curNodes[i] ][ j ];
			}
		}
 
		if( query( curL , curR , vLeft , vRight ) == 1 ) break;
      
      	sz = sz/2;
	}
 
	int qtdWhite = 0;
 
	for(int i = 0 ; i < curNodes.size() ; i++)
		if( i%sz >= sz/2 ) white[ qtdWhite++ ] = curNodes[ i ];
 
	int p = 0;
 
	black[0].clear();
 
	bool change = false;
 
	for(int i = 0 ; i < curNodes.size() ; i++)
	{
		if( i%sz < sz/2 )
		{
			if( change ) 
			{
				p++;
				black[p].clear();
				change = false;
			}
 
			for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
				black[ p ].push_back( nodes[ curNodes[i] ][ j ] );
 
			//black[ p ].push_back( curNodes[i] ), printf("i = %d  p = %d %d\n",i,p,black[p][i]);
		}
		else change = true;
	}
 
	int L = 0;
	int R = p - 1;
 
	while( L < R )
	{
		int m = ( L + R )/2;
 
		p = 0;
 
		for(int i = L ; i <= m ; i++)
			for(int j = 0 ; j < black[i].size() ; j++)
				aux[ p++ ] = black[i][j];
 
		if( query( qtdWhite , p , white , aux ) == 1 ) R = m;
		else L = m + 1;
	}
 
	Left.clear();
	Right.clear();
 
	for(int i = 0 ; i < black[L].size() ; i++)
		Left.push_back( black[L][i] );//, printf("l %d\n",black[L][i]);
 
	for(int i = L*sz ; i < curNodes.size() && i < ( L + 1 )*sz ; i++)
	{
		if( i%sz >= sz/2 ) 
		{
			for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
				Right.push_back( nodes[ curNodes[i] ][j] );//, printf("r %d\n",Right.back());
		}
	}
}
 
/*void setRoad(int a, int b)
{
	printf("========================================= %d %d\n",a,b);
}*/
 
void run(int n)
{
	for(int i = 1 ; i <= n ; i++)
	{
		pai[ i ] = i;
		nodes[ i ].push_back( i );
	}
 
	for(int k = 1 ; k < n ; k++)
	{
		curNodes.clear();
		memset( marc , false , sizeof(marc) );
 
		for(int i = 1 ; i <= n ; i++)
		{
			int cur = find( i );
 
			if( !marc[ cur ] )
			{
				//printf("entrou %d\n",cur);
				marc[ cur ] = true;
				curNodes.push_back( cur );
			}
		}
 
		bsPieces();
 
		int componentU = bsComponent();
 
		//printf("componentU = %d\n",componentU);
 
		swap( Left , Right );
 
		Left.clear();
		Left.push_back( componentU );
 
		int componentV = bsComponent();
 
		componentU = find( componentU );
		componentV = find( componentV );
 
		//printf("componentV = %d\n",componentV);
 
		Left.clear();
		Right.clear();
 
		for(int i = 0 ; i < nodes[ componentU ].size() ; i++)
			Left.push_back( nodes[ componentU ][i] );//, printf("lllllll %d\n",Left.back());
 
		for(int i = 0 ; i < nodes[ componentV ].size() ; i++)
			Right.push_back( nodes[ componentV ][i] );//, printf("rrrr %d\n",Right.back());
 
		int U = bsComponent();
 
		//printf("U = %d\n",U);
 
		swap( Left , Right );
 
		Left.clear();
		Left.push_back( U );
 
		int V = bsComponent();
 
		join( U , V );
		setRoad( U , V );
	}
}
 
/*int main()
{
	int n;
	scanf("%d",&n);
 
	run( n );
}*/

Compilation message (stderr)

icc.cpp: In function 'int bsComponent()':
icc.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < Left.size() ; i++)
                  ~~^~~~~~~~~~~~~
icc.cpp: In function 'void bsPieces()':
icc.cpp:99:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < curNodes.size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
icc.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:108:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < curNodes.size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
icc.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < curNodes.size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
icc.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:158:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < black[i].size() ; j++)
                    ~~^~~~~~~~~~~~~~~~~
icc.cpp:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < black[L].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
icc.cpp:171:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = L*sz ; i < curNodes.size() && i < ( L + 1 )*sz ; i++)
                     ~~^~~~~~~~~~~~~~~~~
icc.cpp:175:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:232:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < nodes[ componentU ].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:235:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < nodes[ componentV ].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10