| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 963983 |
2024-04-16T06:58:48 Z |
LucaIlie |
ICC (CEOI16_icc) |
C++17 |
|
100 ms |
856 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100;
int leader[MAX_N + 1];
vector<int> group[MAX_N + 1];
bool qry( vector<int> a, vector<int> b ) {
int aa[a.size()], bb[b.size()];
for ( int i = 0; i < a.size(); i++ )
aa[i] = a[i];
for ( int i = 0; i < b.size(); i++ )
bb[i] = b[i];
return query( a.size(), b.size(), aa, bb );
}
int bit;
int solveA( vector<int> a, vector<int> b ) {
if ( a.size() == 1 )
return a[0];
vector<int> a1, a2;
for ( int i = 0; i < a.size() / 2; i++ )
a1.push_back( a[i] );
for ( int i = a.size() / 2; i < a.size(); i++ )
a2.push_back( a[i] );
if ( qry( a1, b ) )
return solveA( a1, b );
return solveA( a2, b );
}
int solveB( vector<int> a, vector<int> b ) {
if ( b.size() == 1 )
return b[0];
vector<int> b1, b2;
for ( int i = 0; i < b.size() / 2; i++ )
b1.push_back( b[i] );
for ( int i = b.size() / 2; i < b.size(); i++ )
b2.push_back( b[i] );
if ( qry( a, b1 ) )
return solveB( a, b1 );
return solveB( a, b2 );
}
void run( int n ) {
for ( int v = 1; v <= n; v++ ) {
leader[v] = v;
group[v].push_back( v );
}
for ( int pas = 0; pas < n - 1; pas++ ) {
vector<vector<int>> g;
for ( int v = 1; v <= n; v++ ) {
if ( leader[v] == v )
g.push_back( group[v] );
}
int p = 0;
while ( 1 ) {
vector<int> s[2];
for ( int i = 0; i < g.size(); i++ ) {
int b = (i >> p) & 1;
for ( int v: g[i] )
s[b].push_back( v );
}
if ( qry( s[0], s[1] ) ) {
int first = solveA( s[0], s[1] );
int j = 0;
for ( int i = 0; i < g.size(); i++ ) {
for ( int v: g[i] ) {
if ( v == first )
j = i;
}
}
s[0].clear();
s[1].clear();
s[0].push_back( first );
for ( int i = 0; i < g.size(); i++ ) {
bool ok = true;
for ( int b = 0; b < p; b++ ) {
if (((j >> b) & 1) != ((i >> b) & 1))
ok = false;
}
if ( ((j >> p) & 1) == ((i >> p) & 1) )
ok = false;
if ( ok ) {
for ( int v: g[i] )
s[1].push_back( v );
}
}
int second = solveB( s[0], s[1] );
setRoad( first, second );
int x = leader[first], y = leader[second];
for ( int v: group[y] ) {
leader[v] = x;
group[x].push_back( v );
}
group[y].clear();
break;
}
p++;
}
}
}
Compilation message
icc.cpp: In function 'bool qry(std::vector<int>, std::vector<int>)':
icc.cpp:12:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for ( int i = 0; i < a.size(); i++ )
| ~~^~~~~~~~~~
icc.cpp:14:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for ( int i = 0; i < b.size(); i++ )
| ~~^~~~~~~~~~
icc.cpp: In function 'int solveA(std::vector<int>, std::vector<int>)':
icc.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for ( int i = 0; i < a.size() / 2; i++ )
| ~~^~~~~~~~~~~~~~
icc.cpp:27:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for ( int i = a.size() / 2; i < a.size(); i++ )
| ~~^~~~~~~~~~
icc.cpp: In function 'int solveB(std::vector<int>, std::vector<int>)':
icc.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for ( int i = 0; i < b.size() / 2; i++ )
| ~~^~~~~~~~~~~~~~
icc.cpp:41:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for ( int i = b.size() / 2; i < b.size(); i++ )
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for ( int i = 0; i < g.size(); i++ ) {
| ~~^~~~~~~~~~
icc.cpp:75:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for ( int i = 0; i < g.size(); i++ ) {
| ~~^~~~~~~~~~
icc.cpp:84:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for ( int i = 0; i < g.size(); i++ ) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Ok! 96 queries used. |
| 2 |
Correct |
4 ms |
604 KB |
Ok! 100 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
604 KB |
Ok! 520 queries used. |
| 2 |
Correct |
34 ms |
600 KB |
Ok! 543 queries used. |
| 3 |
Correct |
23 ms |
600 KB |
Ok! 543 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
648 KB |
Ok! 1283 queries used. |
| 2 |
Correct |
76 ms |
640 KB |
Ok! 1293 queries used. |
| 3 |
Correct |
64 ms |
652 KB |
Ok! 1223 queries used. |
| 4 |
Correct |
73 ms |
644 KB |
Ok! 1310 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
604 KB |
Ok! 1292 queries used. |
| 2 |
Correct |
72 ms |
856 KB |
Ok! 1308 queries used. |
| 3 |
Correct |
75 ms |
640 KB |
Ok! 1290 queries used. |
| 4 |
Correct |
67 ms |
636 KB |
Ok! 1252 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
856 KB |
Ok! 1323 queries used. |
| 2 |
Correct |
71 ms |
648 KB |
Ok! 1316 queries used. |
| 3 |
Correct |
72 ms |
636 KB |
Ok! 1311 queries used. |
| 4 |
Correct |
68 ms |
636 KB |
Ok! 1295 queries used. |
| 5 |
Correct |
78 ms |
656 KB |
Ok! 1328 queries used. |
| 6 |
Correct |
86 ms |
636 KB |
Ok! 1291 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
644 KB |
Ok! 1312 queries used. |
| 2 |
Correct |
85 ms |
652 KB |
Ok! 1300 queries used. |
