Submission #545902

#	Time	Username	Problem	Language	Result	Execution time	Memory
545902		rainboy	ICC (CEOI16_icc)	C++98	100 / 100	129 ms	496 KiB

icc

#include "icc.h"
#include <string.h>

#define N	100

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

void run(int n) {
	static int cc[N], ii1[N], ii2[N];
	int h;

	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < n - 1; h++) {
		int n1, n2, i, j, l, l_, c, c1, c2, lower, upper;

		for (i = 0, c = 0; i < n; i++)
			if (ds[i] < 0)
				cc[i] = c++;
		for (i = 0; i < n; i++)
			cc[i] = cc[find(i)];
		c2 = 0, l_ = -1;
		for (l = 0; (1 << l) < c; l++) {
			n1 = 0, n2 = 0;
			for (i = 0; i < n; i++)
				if ((cc[i] & 1 << l) == 0)
					ii1[n1++] = i + 1;
				else
					ii2[n2++] = i + 1;
			if (n1 != 0 && n2 != 0 && query(n1, n2, ii1, ii2))
				c2 |= 1 << l, l_ = l;
		}
		c1 = 0;
		for (l = 0; (1 << l) < c; l++) {
			if (l == l_)
				continue;
			n1 = 0, n2 = 0;
			for (i = 0; i < n; i++)
				if ((cc[i] & ((1 << l) | (1 << l_))) == 0)
					ii1[n1++] = i + 1;
				else
					ii2[n2++] = i + 1;
			if (n1 == 0 || n2 == 0 || !query(n1, n2, ii1, ii2))
				c1 |= 1 << l;
		}
		c2 ^= c1;
		n1 = 0, n2 = 0;
		for (i = 0; i < n; i++)
			if (cc[i] == c1)
				ii1[n1++] = i + 1;
			else if (cc[i] == c2)
				ii2[n2++] = i + 1;
		lower = 0, upper = n1;
		while (upper - lower > 1) {
			int g = (lower + upper) / 2;

			if (query(g - lower, n2, ii1 + lower, ii2))
				upper = g;
			else
				lower = g;
		}
		i = ii1[lower] - 1;
		lower = 0, upper = n2;
		while (upper - lower > 1) {
			int g = (lower + upper) / 2;

			if (query(n1, g - lower, ii1, ii2 + lower))
				upper = g;
			else
				lower = g;
		}
		j = ii2[lower] - 1;
		setRoad(i + 1, j + 1), join(i, j);
	}
}

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