Submission #1244531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244531		lovrot	ICC (CEOI16_icc)	C++20	100 / 100	100 ms	708 KiB

icc

#define db(...) fprintf(stderr, __VA_ARGS__)
#include "icc.h"
#include <cstdio>
#include <random>
#include <chrono>
#include <algorithm>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int, int> pii;

const int N = 110;

int n, un[N];

int trazi(int u) { return un[u] == u ? u : un[u] = trazi(un[u]); }

void unija(int u, int v) { 
	u = trazi(u);
	v = trazi(v);
	un[u] = v;
}

void include(int u, vector<int> &v) { 
	for(int i = 1; i <= n; ++i) { 
		if(trazi(i) == u) { v.PB(i); }
	}
}

bool _query(vector<int> &a, vector<int> &b) { 
	int s = a.size(), s_ = b.size();
	int x[s], y[s_];
	for(int i = 0; i < s; ++i) { x[i] = a[i]; }
	for(int i = 0; i < s_; ++i) { y[i] = b[i]; }
	return query(s, s_, x, y);
}

bool __query(vector<vector<int>> &a, vector<vector<int>> &b) {
	vector<int> A, B;
	for(auto &i : a) { 
		for(int x : i) { include(x, A); }
	}
	for(auto &i : b) { 
		for(int x : i) { include(x, B); }
	}
	return _query(A, B);
}

void debug(vector<int> &v, const char c[]) { 
	for(int x : v) db("%d ", x);
	db("%s", c);
}

void findhalf(vector<int> &a, vector<int> &b, vector<int> u) { 
	vector<vector<int>> A, B;
	A.PB({});
	B.PB({});
	for(int i = 0; i < (int) u.size(); ++i) { 
		if(i < (int) u.size() / 2) { A[0].PB(u[i]); }
		else { B[0].PB(u[i]); }
	}

	for(; !__query(A, B); ) { 
		if(A.empty() && B.empty()) { exit(0); }
//		for(auto &i : A) debug(i, ""); 
//		db("| ");
//		for(auto &i : B) debug(i, ""); 
//		db("\n");

		vector<vector<int>> A_, B_;
		for(auto &i : A) { 
			if((int) i.size() <= 1) { continue; }
			vector<int> a, b;
			for(int j = 0; j < (int) i.size(); ++j) { 
				if(j < (int) i.size() / 2) { a.PB(i[j]); }
				else { b.PB(i[j]); }
			}
			A_.PB(a);
			B_.PB(b);
		}
		for(auto &i : B) { 
			if((int) i.size() <= 1) { continue; }
			vector<int> a, b;
			for(int j = 0; j < (int) i.size(); ++j) { 
				if(j < (int) i.size() / 2) { a.PB(i[j]); }
				else { b.PB(i[j]); }
			}
			A_.PB(a);
			B_.PB(b);
		}
		A = A_;
		B = B_;
	}

	for(auto &i : A) { for(int x : i) { a.PB(x); } }
	for(auto &i : B) { for(int x : i) { b.PB(x); } }
}

int binsearch(vector<int> &a, vector<int> &b) { 
	int lo = -1, hi = (int) a.size() - 1;
	for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
		vector<int> a_;
		for(int i = 0; i <= mi; ++i) { a_.PB(a[i]); }
		if(_query(a_, b)) { hi = mi; }
		else { lo = mi; }
	}

	return a[hi];
}

void run(int nn) { 
	n = nn;
	for(int i = 1; i <= n; ++i) { un[i] = i; }

	for(int ii = 0; ii < n - 1; ++ii) { 
		vector<int> u, a, b;
		for(int i = 1; i <= n; ++i) { 
			if(trazi(i) == i) { u.PB(i); }
		}

		debug(u, "unions\n");

		findhalf(a, b, u);

		vector<int> A, B;
		for(int i : a) { include(i, A); }
		for(int i : b) { include(i, B); }

		debug(A, "A\n");
		debug(B, "B\n");

		int x = binsearch(A, B);
		int y = binsearch(B, A);

		db(">>> %d - %d <<<\n", x, y);
		setRoad(x, y);
		unija(x, y);
	}

	return;
}

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