| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 963657 | LucaIlie | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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] );
}
int s = 0;
while ( 1 ) {
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
shuffle( g.begin(), g.end(), default_random_engine( seed ) );
int x = g.size() / 3 + rand() % (g.size() / 3);
x = max( g.size() - 1, x );
vector<int> a, b;
for ( int i = 0; i < x; i++ ) {
for ( int v: g[i] )
a.push_back( v );
}
for ( int i = x; i < g.size(); i++ ) {
for ( int v: g[i] )
b.push_back( v );
}
s++;
/*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";*/
if ( qry( a, b ) ) {
auto 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;
}
}
}
}