Submission #706937

#	Time	Username	Problem	Language	Result	Execution time	Memory
706937		SanguineChameleon	ICC (CEOI16_icc)	C++17	90 / 100	146 ms	596 KiB

icc

#include <bits/stdc++.h>
using namespace std;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

#ifndef KAMIRULEZ

#include <icc.h>

#endif

using namespace std;

#ifdef KAMIRULEZ

int pt = 0;
pair<int, int> e[120];
bool f[120][120];

int query(int size_a, int size_b, int a[], int b[]) {
	for (int i = 0; i < size_a; i++) {
		int u = a[i];
		for (int j = 0; j < size_b; j++) {
			int v = b[j];
			assert(u != v);
		}
	}
	for (int i = 0; i < size_a; i++) {
		int u = a[i];
		for (int j = 0; j < size_b; j++) {
			int v = b[j];
			if (f[u][v]) {
				return 1;
			}
		}
	}
	return 0;
}

void add() {
	int u = e[pt].first;
	int v = e[pt].second;
	f[u][v] = true;
	f[v][u] = true;
}

void setRoad(int u, int v) {
	assert(((e[pt].first == u) && (e[pt].second == v)) || ((e[pt].first == v) && (e[pt].second == u)));
	pt++;
	add();
}

#endif

ostream& operator<<(ostream &out, vector<int> q) {
	int sz = q.size();
	for (int i = 0; i < sz; i++) {
		out << q[i];
		if (i < sz - 1) {
			out << " ";
		}
	}
	return out;
}

int query_vec(vector<int> A, vector<int> B) {
	int a[120] = {};
	int b[120] = {};
	int size_a = A.size();
	int size_b = B.size();
	for (int i = 0; i < size_a; i++) {
		a[i] = A[i];
	}
	for (int i = 0; i < size_b; i++) {
		b[i] = B[i];
	}
	return query(size_a, size_b, a, b);
}

void run(int n) {
	vector<vector<int>> comps;
	for (int i = 1; i <= n; i++) {
		comps.push_back({i});
	}
	for (int k = 0; k < n - 1; k++) {
		vector<int> orig(n - k);
		iota(orig.begin(), orig.end(), 0);
		vector<vector<int>> cur = {orig};
		shuffle(cur.begin(), cur.end(), gen);
		while (true) {
			vector<vector<int>> nxt;
			vector<int> ql;
			vector<int> qr;
			for (auto x: cur) {
				int sz = x.size();
				vector<int> lv(x.begin(), x.begin() + sz / 2);
				vector<int> rv(x.begin() + sz / 2, x.end());
				if (!lv.empty()) {
					nxt.push_back(lv);
					for (auto id: lv) {
						ql.insert(ql.end(), comps[id].begin(), comps[id].end());
					}
				}
				if (!rv.empty()) {
					nxt.push_back(rv);
					for (auto id: rv) {
						qr.insert(qr.end(), comps[id].begin(), comps[id].end());
					}
				}
			}
			if (query_vec(ql, qr)) {
				shuffle(ql.begin(), ql.end(), gen);
				shuffle(qr.begin(), qr.end(), gen);
				while (true) {
					int sz = ql.size();
					if (sz == 1) {
						break;
					}
					vector<int> lv(ql.begin(), ql.begin() + sz / 2);
					vector<int> rv(ql.begin() + sz / 2, ql.end());
					if (!lv.empty() && query_vec(lv, qr)) {
						ql = lv;
					}
					else {
						ql = rv;
					}
				}
				while (true) {
					int sz = qr.size();
					if (sz == 1) {
						break;
					}
					vector<int> lv(qr.begin(), qr.begin() + sz / 2);
					vector<int> rv(qr.begin() + sz / 2, qr.end());
					if (!lv.empty() && query_vec(lv, ql)) {
						qr = lv;
					}
					else {
						qr = rv;
					}
				}
				int u = ql[0];
				int v = qr[0];
				int cu = -1;
				int cv = -1;
				for (int i = 0; i < n - k; i++) {
					for (auto x: comps[i]) {
						if (u == x) {
							cu = i;
							break;
						}
					}
				}
				for (int i = 0; i < n - k; i++) {
					for (auto x: comps[i]) {
						if (v == x) {
							cv = i;
							break;
						}
					}
				}
				comps[cu].insert(comps[cu].end(), comps[cv].begin(), comps[cv].end());
				comps.erase(comps.begin() + cv);
				setRoad(u, v);
				break;
			}
			else {
				cur.swap(nxt);
			}
		}
	}
}

#ifdef KAMIRULEZ

int main() {
	freopen("kamirulez.inp", "r", stdin);
	freopen("kamirulez.out", "w", stdout);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		e[i] = {u, v};
	}
	add();
	run(n);
}

#endif

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