Submission #918835

#	Time	Username	Problem	Language	Result	Execution time	Memory
918835		vjudge1	ICC (CEOI16_icc)	C++17	100 / 100	104 ms	856 KiB

icc

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#include "icc.h"
 
const int N = 200;
 
vector<int> g[N] , par(N , -1) , adj;
 
int union_find(int x) {
	if(par[x] == x) {
		return x;
	}
	par[x] = union_find(par[x]);
	return par[x];
}
 
void union_set(int x, int y) {
	x = union_find(x);
	y = union_find(y);
 
	if(x == y) {
		return;
	}
	if(g[x].size() < g[y].size()) {
		swap(x,y);
	}
	par[y] = x;
	for(auto i : g[y]) {
		g[x].push_back(i);
	}
	g[y].clear();
}
 
mt19937 rng(time(NULL));
 
void run(int n) {
	for(int i=1;i<=n;i++) {
		par[i] = i;
		g[i].push_back(i);
	}
 
	for(int p=0;p<n - 1;p++) {
		set<int> s;
		adj.clear();
		for(int i=1;i<=n;i++) {
			s.insert(union_find(i));
		}
		for(auto i : s) {
			adj.push_back(i);
		}
		shuffle(adj.begin(), adj.end() , rng);
		vector<int>a,b;
		for(int mask = 0;mask < 8;mask++) {
			vector<int> fi, se;
			for(int i=0;i<(int)adj.size();i++) {
				if(i & (1 << mask)) {
					for(auto j : g[adj[i]]) {
						fi.push_back(j);
					}
				}
				else {
					for(int j : g[adj[i]]) {
						se.push_back(j);
					}
				}
			}
 
			if(query(fi.size(), se.size(), fi.data(), se.data())) {
				a = fi;
				b = se;
				break;
			}
		}
		int l = 0, r = a.size();
		int res1 = -1 , res2 = -1;
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		
		while(l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for(int i=0;i<=mid;i++) {
				v.push_back(a[i]);
			}
			if(query(v.size(), b.size(), v.data(), b.data())) {
				res1 = v.back();
				r = mid;
			}
			else {
				l = mid+1;
			}
		}
		l = 0, r = b.size();
		while(l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for(int i=0;i<=mid;i++) {
				v.push_back(b[i]);
			}
			if(query(v.size(), a.size(), v.data(), a.data())) {
				res2 = v.back();
				r = mid;
			} 
			else {
				l = mid+1;
			}
		}
		union_set(res1, res2);
		setRoad(res1, res2);
	}
}

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