Submission #977612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977612	2024-05-08T07:37:39 Z	happypotato	Mechanical Doll (IOI18_doll)	C++17	16 / 100	67 ms	12812 KB

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.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	30 ms	7768 KB	Output is correct
3	Correct	26 ms	7516 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	8 ms	1884 KB	Output is correct
6	Correct	39 ms	11100 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	30 ms	7768 KB	Output is correct
3	Correct	26 ms	7516 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	8 ms	1884 KB	Output is correct
6	Correct	39 ms	11100 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	40 ms	8476 KB	Output is correct
9	Correct	53 ms	10768 KB	Output is correct
10	Correct	55 ms	12628 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	30 ms	7768 KB	Output is correct
3	Correct	26 ms	7516 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	8 ms	1884 KB	Output is correct
6	Correct	39 ms	11100 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	40 ms	8476 KB	Output is correct
9	Correct	53 ms	10768 KB	Output is correct
10	Correct	55 ms	12628 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	67 ms	12812 KB	Output is correct
15	Correct	40 ms	6976 KB	Output is correct
16	Correct	52 ms	10444 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	61 ms	12568 KB	Output is correct
21	Correct	1 ms	344 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct