| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 963687 |
2024-04-15T13:22:33 Z |
LucaIlie |
ICC (CEOI16_icc) |
C++17 |
|
239 ms |
932 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 );
}
pair<int, int> solve( vector<int> a, vector<int> b ) {
if ( b.size() == 1 ) {
if ( a.size() == 1 )
return { a[0], b[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 solve( a1, b );
return solve( a2, b );
}
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 solve( a, b1 );
return solve( a, b2 );
}
void run( int n ) {
for ( int v = 1; v <= n; v++ ) {
leader[v] = v;
group[v].push_back( v );
}
for ( int i = 0; i < n - 1; i++ ) {
vector<vector<int>> g;
for ( int v = 1; v <= n; v++ ) {
if ( leader[v] == v )
g.push_back( group[v] );
}
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
shuffle( g.begin(), g.end(), default_random_engine( seed ));
/*for ( int i = 0; i < a.size(); i++ )
cout << a[i] << " ";
cout << "\n";
for ( int i = 0; i < b.size(); i++ )
cout << b[i] << " ";
cout << "\n";
cout << "\n";*/
queue<vector<vector<int>>> q;
q.push( g );
while ( !q.empty() ) {
vector<vector<int>> c = q.front();
q.pop();
if ( c.size() <= 1 )
continue;
/*printf( "%d\n", c.size() );
for ( auto g: c ) {
for ( auto v: g )
cout << v << " ";
cout << "\n";
}
printf( "\n" );*/
vector<int> a, b;
for ( int i = 0; i < c.size() / 2; i++ ) {
for ( int v: c[i] )
a.push_back( v );
}
for ( int i = c.size() / 2; i < c.size(); i++ ) {
for ( int v: c[i] )
b.push_back( v );
}
if ( qry( a, b ) ) {
pair<int, int> e = solve( a, b );
setRoad( e.first, e.second );
int x = leader[e.first], y = leader[e.second];
for ( int v: group[y] ) {
leader[v] = x;
group[x].push_back( v );
}
group[y].clear();
break;
}
vector<vector<int>> d, e;
for ( int i = 0; i < c.size() / 2; i++ )
d.push_back( c[i] );
for ( int i = c.size() / 2; i < c.size(); i++ )
e.push_back( c[i] );
q.push( d );
q.push( e );
}
while ( !q.empty() )
q.pop();
}
}
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 'std::pair<int, int> solve(std::vector<int>, std::vector<int>)':
icc.cpp:25:28: 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:39: 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:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for ( int i = 0; i < b.size() / 2; i++ )
| ~~^~~~~~~~~~~~~~
icc.cpp:38:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for ( int i = b.size() / 2; i < b.size(); i++ )
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:87:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for ( int i = 0; i < c.size() / 2; i++ ) {
| ~~^~~~~~~~~~~~~~
icc.cpp:91:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for ( int i = c.size() / 2; i < c.size(); i++ ) {
| ~~^~~~~~~~~~
icc.cpp:109:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for ( int i = 0; i < c.size() / 2; i++ )
| ~~^~~~~~~~~~~~~~
icc.cpp:111:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for ( int i = c.size() / 2; i < c.size(); i++ )
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Ok! 104 queries used. |
| 2 |
Correct |
5 ms |
600 KB |
Ok! 108 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
680 KB |
Ok! 789 queries used. |
| 2 |
Correct |
57 ms |
676 KB |
Ok! 1328 queries used. |
| 3 |
Correct |
57 ms |
812 KB |
Ok! 1340 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
932 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
684 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
600 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
712 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
