답안 #977603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977603 2024-05-08T07:30:11 Z happypotato 자동 인형 (IOI18_doll) C++17
0 / 100
29 ms 7916 KB
#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(reidx[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);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 29 ms 7916 KB wrong motion
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 29 ms 7916 KB wrong motion
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 29 ms 7916 KB wrong motion
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -