Submission #229327

#	Time	Username	Problem	Language	Result	Execution time	Memory
229327		islingr	ICC (CEOI16_icc)	C++14	100 / 100	160 ms	760 KiB

icc

#include <icc.h>
#include <iostream>
#include <vector>

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
#define sz(x) int((x).size())
 
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;

vector<vi> comp;

bool query(vi &a, vi &b) {
	return query(sz(a), sz(b), a.data(), b.data());
}

bool query_comp(vi &a, vi &b) {
	vi x, y;
	for (int c : a) for (int v : comp[c]) x.eb(v);
	for (int c : b) for (int v : comp[c]) y.eb(v);
	return query(x, y);
}

void merge(int a, int b) {
	copy(begin(comp[b]), end(comp[b]), back_inserter(comp[a]));
	comp.erase(begin(comp) + b);
}

pii dnc(vi a, vi b) {
	if (sz(a) < sz(b)) swap(a, b); // sz(b) <= sz(a)
	if (sz(a) == 1 && sz(b) == 1) return {a[0], b[0]};
	int mid = (sz(a) + 1)/ 2;
	vi l(begin(a), begin(a) + mid), r(begin(a) + mid, end(a));
	if (query(l, b)) return dnc(l, b);
	return dnc(r, b);
}

void run(int n) {
	rep(i, 0, n) comp.eb(vi{i + 1});
	rep(i, 1, n) {
		int axb = 0;
		for (int j = 0; (1 << j) <= sz(comp); ++j) {
			vi a, b;
			rep(k, 0, sz(comp))
				if (k & 1 << j) a.eb(k);
				else b.eb(k);
			if (query_comp(a, b))
				axb |= 1 << j;
		}
		
		int x; for (x = 0; ~axb & 1 << x; ++x);
		int l = 1 << x, r = 0;
		for (int j = 0; (1 << j) <= sz(comp); ++j) {
			if (j == x) continue;
			vi a, b;
			if (axb & 1 << j) {
				rep(k, 0, sz(comp))
					if (k & 1 << x) { if (k & 1 << j) a.eb(k); }
					else { if (~k & 1 << j) b.eb(k); }
				if (query_comp(a, b)) l |= 1 << j;
				else r |= 1 << j;
			} else {
				rep(k, 0, sz(comp))
					if (k & 1 << j) {
						if (k & 1 << x) a.eb(k);
						else b.eb(k);
					}
				if (query_comp(a, b)) {
					l |= 1 << j;
					r |= 1 << j;
				}
			}
		}

		pii p = dnc(comp[l], comp[r]);
		merge(l, r);
		setRoad(p.first, p.second);
	}
}

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