제출 #259401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259401		youssefbou62	ICC (CEOI16_icc)	C++14	0 / 100	9 ms	896 KiB

icc

#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((g1!=-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) ; 
// }

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10