Submission #978151

#	Time	Username	Problem	Language	Result	Execution time	Memory
978151		happypotato	Mechanical Doll (IOI18_doll)	C++17	53 / 100	106 ms	16616 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
void create_circuit(int m, vector<int> a) {
	int n = a.size();
	int reidx[m + 1];
	for (int i = 1; i <= m; i++) reidx[i] = 0;
	for (int x : a) reidx[x]++;
	int bruh[m + 1];
	for (int i = 1; i < n; i++) bruh[a[i - 1]] = a[i];
	bruh[a[n - 1]] = 0;
	int base = 0;
	vector<int> C(m + 1);
	C[0] = a[0];
	for (int i = 1; i <= m; i++) {
		if (reidx[i] == 0) {
			C[i] = 0;
		} else if (reidx[i] == 1) {
			C[i] = bruh[i];
			reidx[i] = 0;
		} else if (reidx[i] >= 2) {
			reidx[i] = ++base;
			C[i] = -reidx[i];
		}
	}
 
	vector<int> sto[base + 1];
	for (int i = 1; i < n; i++) {
		sto[reidx[a[i - 1]]].pb(a[i]);
	}
	sto[reidx[a[n - 1]]].pb(0);
	// for (int i = 1; i <= m; i++) cerr << reidx[i] << ' ';
	// cerr << endl;
	// for (int i = 1; i <= base; i++) {
	// 	for (int x : sto[i]) cerr << x << ' ';
	// 	cerr << endl;
	// }
 
	vector<pii> nxt[2];
	bool flag = false;
	vector<int> access;
	vector<bool> state;
	auto gentree = [&](auto&& self, int sz) {
		if (sz == 2) {
			nxt[flag] = {{-2, -2}};
			return;
		}
		self(self, (sz + 1) / 2);
		flag ^= 1;
		nxt[flag] = {{-1, -1}};
		for (int i = 0; i < 2; i++) {
			int buff = nxt[flag].size();
			if (i == 0) nxt[flag][0].ff = buff;
			else nxt[flag][0].ss = buff;
			for (pii cur : nxt[flag ^ 1]) {
				if (cur.ff != -2) cur.ff += buff;
				if (cur.ss != -2) cur.ss += buff;
				nxt[flag].pb(cur);
			}
		}
		if (sz % 2 == 1) {
			access.resize(nxt[flag].size(), 0);
			int st = 0;
			while (true) {
				if (!access[st]) {
					access[st] = !access[st];
					if (nxt[flag][st].ff == -2) {
						nxt[flag][st].ff = 0; break;
					}
					st = nxt[flag][st].ff;
				} else {
					access[st] = !access[st];
					if (nxt[flag][st].ss == -2) {
						nxt[flag][st].ss = 0; break;
					}
					st = nxt[flag][st].ss;
				}
			}
		}
	};
	auto gen = [&](auto&& self, int sz) -> int {
		nxt[0].clear(); nxt[1].clear();
		flag = false;
		gentree(gentree, sz);
		int used = nxt[flag].size();
		int dirs = used;
		state.resize(used, 0);
		access.clear();
		int cnt = 0;
		// cerr << "Gen size " << sz << ":\n";
		// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
		// cerr << "End" << endl;
		do {
			int st = 0;
			while (true) {
				if (!state[st]) {
					state[st] = !state[st]; cnt++;
					if (nxt[flag][st].ff == -2) {
						nxt[flag][st].ff = dirs++;
						break;
					} else {
						st = nxt[flag][st].ff;
					}
				} else {
					state[st] = !state[st]; cnt--;
					if (nxt[flag][st].ss == -2) {
						nxt[flag][st].ss = dirs++;
						break;
					} else {
						st = nxt[flag][st].ss;
					}
				}
			}
		} while (cnt > 0);
		// cerr << "Gen size " << sz << ":\n";
		// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
		// cerr << "End" << endl;
		return used;
	};
 
	vector<int> X(base), Y(base);
	int cnt = base;
	for (int i = 1; i <= base; i++) {
		if (sto[i].size() == 1) {
			X[i - 1] = -i;
			Y[i - 1] = sto[i].front();
			continue;
		}
		int assign = gen(gen, sto[i].size());
 
		auto decrypt = [&](int x) -> int {
			if (x == 0) return -i;
			else if (x < assign) return -(x + cnt);
			else return sto[i][x - assign];
		};
		// cerr << "Gen " << i << ": \n";
		// cerr << assign << endl;
		// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
		// cerr << "End of gen " << i << endl;
		X[i - 1] = decrypt(nxt[flag][0].ff); Y[i - 1] = decrypt(nxt[flag][0].ss);
		for (int j = 1; j < (int)(nxt[flag].size()); j++) {
			// cerr << "decrypt " << nxt[j].ff << ' ' << decrypt(nxt[j].ff) << endl;
			X.pb(decrypt(nxt[flag][j].ff));
			Y.pb(decrypt(nxt[flag][j].ss));
		}
		cnt = (int)(X.size());
	}
 
	answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56