Submission #978212

#	Time	Username	Problem	Language	Result	Execution time	Memory
978212		happypotato	Mechanical Doll (IOI18_doll)	C++17	100 / 100	82 ms	11576 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(); a.pb(0);
	vector<int> C(m + 1, -1);
	C[0] = a[0];

	vector<pii> nxt;
	vector<int> access;
	vector<bool> state;
	auto recur = [&](auto&& self, int ptr, int dep, int rem) -> int {
		if (rem <= 0) {
			nxt[ptr] = {ptr, 0};
			return 0;
		}
		// assign right
		if (dep == 1) {
			nxt[ptr].ss = -2;
			rem--;
		} else {
			int nptr = nxt.size();
			nxt[ptr].ss = nptr;
			nxt.pb({-1, -1});
			rem = self(self, nptr, dep - 1, rem);
		}
		// assign left
		if (rem == 0) {
			nxt[ptr].ff = 0;
		} else if (dep == 1) {
			nxt[ptr].ff = -2;
			rem--;
		} else {
			int nptr = nxt.size();
			nxt[ptr].ff = nptr;
			nxt.pb({-1, -1});
			rem = self(self, nptr, dep - 1, rem);
		}
		return rem;
	};
	auto gen = [&](auto&& self, int sz) -> int {
		int logsz = 1;
		while ((1 << logsz) < sz) logsz++;
		nxt = {{-1, -1}};
		recur(recur, 0, logsz, sz);
		int used = nxt.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, nxt size = " << nxt.size() << endl;
		do {
			int st = 0;
			while (true) {
				if (!state[st]) {
					state[st] = !state[st]; cnt++;
					if (nxt[st].ff == -2) {
						nxt[st].ff = dirs++;
						break;
					} else {
						st = nxt[st].ff;
					}
				} else {
					state[st] = !state[st]; cnt--;
					if (nxt[st].ss == -2) {
						nxt[st].ss = dirs++;
						break;
					} else {
						st = nxt[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, Y;
	int assign = gen(gen, n);
	auto decrypt = [&](int x) -> int {
		if (x < assign) return -(x + 1);
		else return a[x - assign + 1];
	};
	for (pii cur : nxt) {
		X.pb(decrypt(cur.ff));
		Y.pb(decrypt(cur.ss));
	}
 
	answer(C, X, Y);
}

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