Submission #1244550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244550		Tob	ICC (CEOI16_icc)	C++20	100 / 100	67 ms	628 KiB

icc

#include <bits/stdc++.h>

#include "icc.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 101;

int n;
int a[N], b[N], par[N], siz[N];
vector <int> c[N];

int find(int x) {return x == par[x] ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (siz[x] < siz[y]) swap(x, y);
	par[y] = x;
	siz[x] += siz[y];
	for (auto it : c[y]) c[x].pb(it);
}

pii f(vector <int> v) {
//	for (auto it : v) cout << it << " "; cout << "F" << endl;
	vector <int> g, h;
	int sa, sb;
	pii p;
	vector <int> wh(n+1);
	int e = 0;
	for (int i = 10; i >= 0; i--) if ((1 << i) < v.size()) {
		sa = 0; sb = 0;
		for (int j = 0; j < v.size(); j++) {
			if (j & (1 << i)) for (int x : c[v[j]]) b[sb++] = x, wh[x] = j;
			else for (int x : c[v[j]]) a[sa++] = x, wh[x] = j;
		}
//		for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
//		for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
		if (query(sa, sb, a, b)) {
			for (int i = 0; i < sa; i++) g.pb(a[i]);
			for (int i = 0; i < sb; i++) h.pb(b[i]);
			e = i;
			break;
		}
	}
//	cout << "CP1 " << g.size() << " " << h.size() << endl;

	sb = 0;
	for (int i = 0; i < h.size(); i++) b[sb++] = h[i];
	int lo = 0, hi = g.size()-1;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		sa = 0;
		for (int i = 0; i <= mid; i++) a[sa++] = g[i];
//		for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
//		for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
		if (query(sa, sb, a, b)) hi = mid;
		else lo = mid+1;
	}
	p.F = g[lo];
	
//	cout << p.F << " " << wh[p.F] << "\n";
	vector <int> hh;
	for (int x : h) {
		if (wh[x]/(1<<e+1) == wh[p.F]/(1<<e+1)) hh.pb(x);
//		cout << wh[x] << " ";
	}
//	cout << " h\n";
	swap(h, hh);
//	for (auto it : h) cout << it << " "; cout << "\n";
//	cout << "CP2 " << g.size() << " " << h.size() << endl;
	sa = 0;
	for (int i = 0; i < g.size(); i++) a[sa++] = g[i];
	lo = 0, hi = h.size()-1;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		sb = 0;
		for (int i = 0; i <= mid; i++) b[sb++] = h[i];
//		for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
//		for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
		if (query(sa, sb, a, b)) hi = mid;
		else lo = mid+1;
	}
//	cout << "END\n";
	p.S = h[lo];
	return p;
}

void run(int nn) {
	n = nn;
	vector <int> v;
	for (int i = 1; i <= n; i++) v.pb(i), c[i].pb(i), par[i] = i, siz[i] = 1;
	for (int ii = 1; ii < n; ii++) {
		pii p = f(v);
//		cout << "ANS " << p.F << " " << p.S << endl;
		setRoad(p.F, p.S);
		unite(p.F, p.S);
		v.clear();
		for (int i = 1; i <= n; i++) v.pb(find(i));
		sort(all(v));
		v.erase(unique(all(v)), v.end());
//		for (auto it : v) cout << it << " "; cout << " x\n";
	}
}

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