oj.uz

Submission #978212

# Submission time Handle Problem Language Result Execution time Memory
978212 2024-05-09T03:37:47 Z happypotato Mechanical Doll (IOI18_doll) C++17
100 / 100
 82 ms 11576 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(); 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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 28 ms 4500 KB Output is correct
3 Correct 28 ms 4816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 41 ms 6968 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 1 ms 348 KB Output is correct
2 Correct 28 ms 4500 KB Output is correct
3 Correct 28 ms 4816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 41 ms 6968 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 49 ms 7732 KB Output is correct
9 Correct 57 ms 8416 KB Output is correct
10 Correct 77 ms 11576 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 28 ms 4500 KB Output is correct
3 Correct 28 ms 4816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 41 ms 6968 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 49 ms 7732 KB Output is correct
9 Correct 57 ms 8416 KB Output is correct
10 Correct 77 ms 11576 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 74 ms 11104 KB Output is correct
15 Correct 50 ms 7212 KB Output is correct
16 Correct 73 ms 10872 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 81 ms 11436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 45 ms 6876 KB Output is correct
3 Correct 46 ms 6860 KB Output is correct
4 Correct 72 ms 10304 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 45 ms 6876 KB Output is correct
3 Correct 46 ms 6860 KB Output is correct
4 Correct 72 ms 10304 KB Output is correct
5 Correct 77 ms 10732 KB Output is correct
6 Correct 72 ms 10604 KB Output is correct
7 Correct 82 ms 10836 KB Output is correct
8 Correct 71 ms 10516 KB Output is correct
9 Correct 53 ms 6864 KB Output is correct
10 Correct 71 ms 10412 KB Output is correct
11 Correct 70 ms 10156 KB Output is correct
12 Correct 46 ms 6868 KB Output is correct
13 Correct 47 ms 6956 KB Output is correct
14 Correct 48 ms 7096 KB Output is correct
15 Correct 49 ms 7060 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 45 ms 6872 KB Output is correct
18 Correct 54 ms 7148 KB Output is correct
19 Correct 46 ms 7012 KB Output is correct
20 Correct 70 ms 10360 KB Output is correct
21 Correct 69 ms 10424 KB Output is correct
22 Correct 73 ms 10160 KB Output is correct