Submission #1244525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244525		lovrot	ICC (CEOI16_icc)	C++20	61 / 100	121 ms	632 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);
}

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

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");

		for(; 1; ) { 
			shuffle(u.begin(), u.end(), rng);

			a.clear();
			b.clear();
			for(int i = 0; i < (int) u.size(); ++i) { 
				if(i < (int) u.size() / 2) { a.PB(u[i]); }
				else { b.PB(u[i]); }
			}

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

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

		debug(A, "A");
		debug(B, "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; }
		}

		int ans = A[hi];

		lo = -1;
		hi = B.size() - 1;
		for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
			vector<int> B_;
			for(int i = 0; i <= mi; ++i) { B_.PB(B[i]); }
			if(_query(A, B_)) { hi = mi; }
			else { lo = mi; }
		}

		db(">>> %d - %d <<<\n", ans, B[hi]);
		setRoad(ans, B[hi]);
		unija(ans, B[hi]);
	}

	return;
}

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