| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 164449 |
2019-11-20T17:01:22 Z |
Lawliet |
ICC (CEOI16_icc) |
C++14 |
|
586 ms |
632 KB |
#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;
}
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
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:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < curNodes.size() ; i++)
~~^~~~~~~~~~~~~~~~~
icc.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < curNodes.size() ; i++)
~~^~~~~~~~~~~~~~~~~
icc.cpp:138:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < nodes[ curNodes[i] ].size() ; j++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:156:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < black[i].size() ; j++)
~~^~~~~~~~~~~~~~~~~
icc.cpp:166:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < black[L].size() ; i++)
~~^~~~~~~~~~~~~~~~~
icc.cpp:169: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:173: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:230:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < nodes[ componentU ].size() ; i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:233:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < nodes[ componentV ].size() ; i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
504 KB |
Number of queries more than 3000 out of 1500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
409 ms |
632 KB |
Number of queries more than 5000 out of 2500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
586 ms |
564 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
520 ms |
504 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
473 ms |
564 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
427 ms |
568 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
