Submission #24523

#	Time	Username	Problem	Language	Result	Execution time	Memory
24523		rubabredwan	ICC (CEOI16_icc)	C++14	90 / 100	163 ms	2268 KiB

icc

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;
 
const int N = 105;
 
int n, par[N], mat[N][N];
set<int>comp;
vector<int>nudes[N];
 
int Find(int at){
	return par[at] == at ? at : par[at] = Find(par[at]);
}
 
void Union(int a, int b){
	int x = Find(a);
	int y = Find(b);
	for(auto u : nudes[y]){
		nudes[x].push_back(u);
	}
	par[y] = x;
	comp.erase(y);
}

 
int fuk[N], tt;
 
int get(int sa, int sb, int a[], int b[]){
	int lo = 0, hi = sb - 1;
	while(lo < hi){
		int mid = (lo + hi) / 2; tt = 0;
		for(int i=lo;i<=mid;i++) fuk[tt] = b[i], ++tt;
		if(query(sa, tt, a, fuk)) hi = mid;
		else lo = mid + 1;
	}
	return b[lo];
}
 
int aa[N], bb[N], cr[N];
int sa, sb, sz;
 
void run(int _n){
	srand(time(NULL));
	n = _n;
	comp.clear();
	for(int i=1;i<=n;i++){
		par[i] = i;
		comp.insert(i);
		nudes[i].push_back(i);
	}
	for(int road = 1; road < n; ++road){
		sz = 0;
		for(auto u : comp) cr[++sz] = u;
		vector<int>rnd;
		for(int bit = 0; bit <= 7; ++bit) rnd.push_back(bit);
		random_shuffle(rnd.begin(), rnd.end());
		for(auto bit : rnd){
			sa = 0, sb = 0;
			for(int i = 1; i <= sz; ++i){
				if(i & (1 << bit)) for(auto v : nudes[cr[i]]) aa[sa] = v, ++sa;
				else for(auto v : nudes[cr[i]]) bb[sb] = v, ++sb;
			}
			if(sa == 0 || sb == 0) continue;
			if(query(sa, sb, aa, bb)){
				int x = get(sa, sb, aa, bb);
				int y = get(sb, sa, bb, aa);
				Union(x, y);
				setRoad(x, y);
				break;
			}
		}
	}
}

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