Submission #1241119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241119		kaiboy	ICC (CEOI16_icc)	C++20	100 / 100	85 ms	616 KiB

icc

#include <algorithm>
#include <iostream>
#include "icc.h"

using namespace std;

const int N = 100;

int ds[N], rr[N], ii0[N], ii1[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]--;
	if (ds[i] < ds[j])
		swap(i, j);
	ds[i] = j;
}

void run(int n) {
	for (int i = 0; i < n; i++)
		ds[i] = -1;
	for (int z = 0; z < n - 1; z++) {
		int c = 0;
		for (int i = 0; i < n; i++)
			if (ds[i] < 0)
				rr[i] = c++;
		for (int i = 0; i < n; i++)
			rr[i] = rr[find(i)];
		int h_ = -1;
		for (int h = 0; h < 7; h++) {
			int k0 = 0, k1 = 0;
			for (int i = 0; i < n; i++)
				(!(rr[i] >> h & 1) ? ii0[k0++] : ii1[k1++]) = i + 1;
			if (query(k0, k1, ii0, ii1)) {
				h_ = h;
				break;
			}
		}
		int k0 = 0, k1 = 0;
		for (int i = 0; i < n; i++)
			(!(rr[i] >> h_ & 1) ? ii0[k0++] : ii1[k1++]) = i + 1;
		int lower = 0, upper = k0;
		while (upper - lower >> 1) {
			int h = lower + upper >> 1;
			if (query(k0 - h, k1, ii0 + h, ii1))
				lower = h;
			else
				upper = h;
		}
		int i = ii0[lower] - 1;
		lower = 0, upper = k1;
		while (upper - lower >> 1) {
			int h = lower + upper >> 1;
			if (query(k0, k1 - h, ii0, ii1 + h))
				lower = h;
			else
				upper = h;
		}
		int j = ii1[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