| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 | 
|---|---|---|---|---|---|---|---|
| 1241118 | kaiboy | ICC (CEOI16_icc) | C++20 | 0 ms | 0 KiB | 
#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[ii[i] = 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;
		int 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);
	}
}
