Submission #605238

#	Time	Username	Problem	Language	Result	Execution time	Memory
605238		sentheta	ICC (CEOI16_icc)	C++17	100 / 100	141 ms	616 KiB

icc

#include"icc.h"
#include<algorithm>
#include<iostream>
#include<cassert>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
 
#define Int long long
#define V vector
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define dbg(x) cout << "?" << #x << " : " << x << endl; cout.flush();
 
int qry(V<int> a,V<int> b){
	return query(a.size(), b.size(), &a[0], &b[0]);
}
 
const int N = 105;
 
int n;
 
 
V<int> v[N];
int p[N];
int find(int x){
	if(p[x]==x) return x;
	return p[x] = find(p[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
bool unite(int x,int y){
	if((x=find(x))==(y=find(y))) return 0;
 
	for(int i : v[y]) v[x].push_back(i);
	p[y] = x;
	return 1;
}
 
 
void solve(){
 
	// Find possible ccs
	V<int> leads;
	rep(i,1,n+1) if(find(i)==i){
		leads.push_back(i);
	}
	random_shuffle(all(leads));
 
	rep(b,0,7){
		// split into two groups
		V<int> g[2];
		rep(i,0,leads.size()){
			for(int j : v[leads[i]]){
				g[i>>b&1].push_back(j);
			}
		}
		
 
		if(!qry(g[0], g[1])) continue;
		// from here, the answer is between g[0] and g[1]
 
		//for(int i : g[0]) cout << i << " ";
		//cout << endl;
		//for(int i : g[1]) cout << i << " ";
		//cout << endl;
 
		// pinpoint exact node
		rep(i,0,2){
			while(g[i].size() > 1){
				V<int> sg[2];
				rep(j,0,g[i].size()){
					sg[j&1].push_back(g[i][j]);
				}
 
				if(qry(sg[0], g[i^1])){
					g[i] = sg[0];
				}
				else g[i] = sg[1];
			}
			assert(g[i].size()==1);
		}
 
		int p = g[0][0], q = g[1][0];
		//dbg(p); dbg(q);
		unite(p, q);
		setRoad(p, q);
		return;
	}
	assert(0);
 
	
}
 
 
 
void run(int _n){
	n = _n;
	rep(i,0,N){
		v[i] = {i};
		p[i] = i;
	}
 
	rep(i,0,n-1){
		solve();
	}
 
	return;
	//query(1, 2, {1}, {2,3});
	//setRoad(1, 2);
}

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