Submission #1116990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116990		pedroslrey	ICC (CEOI16_icc)	C++17	90 / 100	125 ms	828 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

void run(int n) {
	vector<vector<int>> comps(n);
	vector<int> rep(n);
	for (int i = 0; i < n; ++i) {
		comps[i].push_back(i);
		rep[i] = i;
	}

	auto comp_query = [&](vector<int> &as, vector<int> &bs) {
		static int a[100], b[100];

		int cnta = 0;
		for (int u: as)
			for (int e: comps[u])
				a[cnta++] = e + 1;

		int cntb = 0;
		for (int u: bs)
			for (int e: comps[u])
				b[cntb++] = e + 1;

		return query(cnta, cntb, a, b);
	};

	auto vec_query = [&](vector<int> &as, vector<int> &bs) {
		static int a[100], b[100];

		int cnta = 0;
		for (int u: as)
			a[cnta++] = u + 1;

		int cntb = 0;
		for (int u: bs)
			b[cntb++] = u + 1;

		return query(cnta, cntb, a, b);
	};

	auto turn = [&](int x) {
		vector<int> perm;
		for (int k = 0; k <= __lg(x); ++k)
			perm.push_back(k);

		random_shuffle(perm.begin(), perm.end());

		vector<int> xs, ys;
		for (int k: perm) {
			vector<int> as, bs;
			for (int i = 0; i < x; ++i)
				if (i & (1 << k)) as.push_back(i);
				else bs.push_back(i);

			if (comp_query(as, bs)) {
				for (int l: as)
					for (int u: comps[l])
						xs.push_back(u);

				for (int r: bs)
					for (int u: comps[r])
						ys.push_back(u);
				break;
			}
		}

		// cerr << "SETS:\n";
		// for (int x: xs)
		// 	cerr << x << " ";
		// cerr << "\n";
		// for (int y: ys)
		// 	cerr << y << " ";
		// cerr << "\n";

		int l = 0, r = xs.size();
		while (l < r - 1) {
			int m = (l + r)/2;

			vector<int> qs;
			for (int i = l; i < m; ++i)
				qs.push_back(xs[i]);

			if (vec_query(qs, ys)) r = m;
			else l = m;
		}

		int u = xs[l];

		l = 0, r = ys.size();
		while (l < r - 1) {
			int m = (l + r)/2;

			vector<int> qs;
			for (int i = l; i < m; ++i)
				qs.push_back(ys[i]);

			if (vec_query(qs, xs)) r = m;
			else l = m;
		}

		int v = ys[l];

		return make_pair(u, v);
	};

	auto swap_comps = [&](int a, int b) {
		swap(comps[a], comps[b]);

		for (int u: comps[a]) rep[u] = a;
		for (int v: comps[b]) rep[v] = b;
	};

	for (int i = n; i > 1; --i) {
		auto [u, v] = turn(i);

		swap_comps(rep[u], i - 1);
		swap_comps(rep[v], i - 2);

		for (int u: comps[i-1]) {
			comps[i-2].push_back(u);
			rep[u] = i-2;
		}

		setRoad(u + 1, v + 1);

		cerr << "REP: ";
		for (int r: rep)
			cerr << r << " ";
		cerr << "\n";
	}
}

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