Submission #96035

#	Time	Username	Problem	Language	Result	Execution time	Memory
96035		youngyojun	ICC (CEOI16_icc)	C++11	100 / 100	144 ms	696 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef pair<int, int> pii;
mt19937 mtrd(time(0));

int askA[105], askB[105];
bool ask(vector<int> &A, vector<int> &B) {
	int a = 0, b = 0;
	for(int v : A) askA[a++] = v;
	for(int v : B) askB[b++] = v;
	return query(a, b, askA, askB);
}

vector<int> UV[105];
int ud[105];

int N;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) {
	a = uf(a); b = uf(b);
	if(a == b) return;
	for(int v : UV[b]) UV[a].eb(v);
	UV[b].clear();
	ud[b] = a;
}

void run() {
	vector<int> LV;
	for(int i = 1; i <= N; i++)
		if(uf(i) == i) LV.eb(i);
	shuffle(allv(LV), mtrd);
	int n = sz(LV), x = 0;
	for(int k = 1;; k <<= 1) {
		bool flag = false;
		for(int i = 0; i < n; i++) {
			if(n <= (i^x^k)) continue;
			flag = true;
			break;
		}
		if(!flag) break;
		vector<int> AV, BV;
		for(int i = 0; i < n; i++) {
			auto &V = (i&k) ? AV : BV;
			for(int v : UV[LV[i]]) V.eb(v);
		}
		if(AV.empty() || BV.empty()) continue;
		if(ask(AV, BV)) x |= k;
	}

	vector<pii> EV;
	for(int i = 0, j; i < n; i++) {
		j = i^x;
		if(j <= i || n <= j) continue;
		EV.eb(i, j);
	}
	shuffle(allv(EV), mtrd);
	for(; 1 < sz(EV);) {
		vector<pii> LE, RE;
		int e = sz(EV), m = e >> 1;
		for(int i = 0; i < m; i++) LE.eb(EV[i]);
		for(int i = m; i < e; i++) RE.eb(EV[i]);
		vector<int> AV, BV;
		for(auto &ed : LE) {
			for(int v : UV[LV[ed.first]]) AV.eb(v);
			for(int v : UV[LV[ed.second]]) BV.eb(v);
		}
		swap(EV, ask(AV, BV) ? LE : RE);
	}

	vector<int> AT, BT;
	for(int v : UV[LV[EV[0].first]]) AT.eb(v);
	for(int v : UV[LV[EV[0].second]]) BT.eb(v);
	shuffle(allv(AT), mtrd);
	shuffle(allv(BT), mtrd);
	for(; 1 < sz(AT);) {
		vector<int> AL, AR;
		int e = sz(AT), m = e >> 1;
		for(int i = 0; i < m; i++) AL.eb(AT[i]);
		for(int i = m; i < e; i++) AR.eb(AT[i]);
		swap(AT, ask(AL, BT) ? AL : AR);
	}
	for(; 1 < sz(BT);) {
		vector<int> BL, BR;
		int e = sz(BT), m = e >> 1;
		for(int i = 0; i < m; i++) BL.eb(BT[i]);
		for(int i = m; i < e; i++) BR.eb(BT[i]);
		swap(BT, ask(AT, BL) ? BL : BR);
	}

	{
		int a = AT[0], b = BT[0];
		uf(a, b);
		setRoad(a, b);
	}
}

void run(int _N) {
	N = _N;
	iota(ud, ud+N+1, 0);
	for(int i = 1; i <= N; i++) UV[i].eb(i);
	for(int lq = 1; lq < N; lq++) run();
}

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