제출 #977612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977612		happypotato	자동 인형 (IOI18_doll)	C++17	16 / 100	67 ms	12812 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] = 1;
	int base = 0;
	for (int i = 1; i <= m; i++) {
		if (reidx[i]) reidx[i] = ++base;
	}
	vector<int> C(m + 1);
	C[0] = a[0];
	for (int i = 1; i <= m; i++) {
		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;
	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 left
		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);
		}
		// 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);
		}
		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" << 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);
		int intend = dirs - sz;
		for (pii &cur : nxt) {
			if (cur.ff >= used && cur.ff < intend) cur.ff = 0;
			if (cur.ss >= used && cur.ss < intend) cur.ss = 0;
		}
		return intend;
	};

	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[0].ff); Y[i - 1] = decrypt(nxt[0].ss);
		for (int j = 1; j < (int)(nxt.size()); j++) {
			// cerr << "decrypt " << nxt[j].ff << ' ' << decrypt(nxt[j].ff) << endl;
			X.pb(decrypt(nxt[j].ff));
			Y.pb(decrypt(nxt[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: 0 / 18
• Subtask 6: 0 / 56