| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259400 |
2020-08-07T18:08:24 Z |
youssefbou62 |
ICC (CEOI16_icc) |
C++14 |
|
9 ms |
512 KB |
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
#define sz(x) (int)x.size()
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab (int x ) { return (x>0?x:-x); }
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int MAXN = 105 ;
int n ;
int par[MAXN];
vector<int> groups , inG[MAXN];
void init(int N){
for(int i = 1 ; i <= N ; i++ )par[i] = i , groups.pb(i),inG[i].pb(i);
}
int fs(int u){
if( par[u] == u )return u;
return par[u] = fs(par[u]) ;
}
void us(int u,int v){
u = fs(u) ;
v = fs(v) ;
if( u == v )return ;
par[u] = v ;
}
// int query(int size_a, int size_b, int a[], int b[]){
// cout << "QUERY *********"<<endl;
// cout << size_a << endl;
// for(int i = 0 ; i < size_a ; i++ )cout << a[i] << " " ;cout << endl;
// cout << size_b << endl;
// for(int i = 0 ; i < size_b ; i++ )cout << b[i] << " " ;cout << endl;
// bool x ;
// cin >> x ;
// return x ;
// }
// void setRoad(int a, int b){
// cout << "setRoad "<< a << " " << b << endl;
// return ;
// }
bool ask (vector<int>& a , vector<int>& b){
int A[sz(a)],B[sz(b)];
for(int i = 0 ;i < sz(a) ;i++){
A[i] = a[i];
}
for(int i = 0 ;i <sz(b);i++ )
B[i] = b[i];
return query(sz(a),sz(b),A,B);
}
void run(int N){
n = N ;
init(n);
for(int i = 0 ; i < n-1 ; i++ ){
// for(int g : groups)cout << g <<" " ; cout << endl;
int l = 0 , r = sz(groups)-2 , g1 = -1 , L =-1;
while ( l <= r ){
int mid = ( l + r ) / 2 ;
vector<int> a,b;
// cout <<"/////////"<<endl;
// for(int g : inG[groups[0]])cout << g << " " ; cout << endl; cout<<"////////"<<endl;
for(int x = 0 ; x <= mid ; x++ ){
for(int g : inG[groups[x]]){
a.pb(g);
}
}
for(int x = mid + 1 ; x < sz(groups) ; x++ ){
for(int g : inG[groups[x]])
b.pb(g);
}
if( ask (a,b) ){
r = mid - 1 ;
g1 = groups[mid] ;
L = mid + 1 ;
}else l = mid + 1 ;
}
l=L, r = sz(groups)-1 ;
int g2=-1;
while ( l <= r ){
int mid = ( l + r ) / 2 ;
vector<int> a,b;
a = inG[g1];
for(int x = L ; x <= mid ; x++ )
for(int g : inG[groups[x]])
b.pb(g);
// cout <<"fixed g1 "<<g1<<" "<<endl;
if( ask (a,b) ){
r = mid-1 ;
g2 = groups[mid];
}else l = mid+ 1 ;
}
l = 0 , r = sz(inG[g1])-1;
int res1 = -1 ,res2 =-1;
while ( l <=r ){
int mid = ( l + r )/2 ;
vector<int> a,b;
for(int x = 0 ; x <= mid ; x++ ){
a.pb(inG[g1][x]);
}
if( ask (a,inG[g2]) ){
r = mid-1;
res1 = inG[g1][mid];
}else l = mid + 1 ;
}
l = 0 , r = sz(inG[g2])-1;
// cout << "know res1"<<" "<<res1<<endl;
while ( l <= r ){
int mid = ( l + r )/2 ;
vector<int> a,b;
for(int x = 0 ; x <= mid ; x++ ){
a.pb(inG[g2][x]);
}
b = {res1} ;
if( ask (a,b) ){
r = mid-1;
res2 = inG[g2][mid];
}else l = mid + 1 ;
}
// assert(fs(res1)==g1);
// assert(fs(res2)==g2);
// assert((g2!=-1));
setRoad(res1,res2);
us(res1,res2);
groups.clear();
for(int j = 1 ; j <= n ; j++ )inG[j].clear() ;
for(int j = 1 ; j <= n ; j++ ){
if( find(all(groups),fs(j))== groups.end() )
groups.pb(fs(j)) ;
inG[fs(j)].pb(j) ;
}
}
}
// int main(){
// cin >> n ;
// run(n) ;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
512 KB |
Ok! 134 queries used. |
| 2 |
Incorrect |
1 ms |
512 KB |
Wrong road! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
