oj.uz

Submission #978209

# Submission time Handle Problem Language Result Execution time Memory
978209 2024-05-09T03:31:09 Z happypotato Mechanical Doll (IOI18_doll) C++17
70.6719 / 100
 85 ms 10852 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 (dep == 1) {
			if (rem == 0) {
				nxt[ptr].ff = 0;
			} else {
				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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 592 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Output is partially correct
2 Correct 45 ms 6636 KB Output is correct
3 Partially correct 46 ms 6872 KB Output is partially correct
4 Correct 69 ms 10300 KB Output is correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Output is partially correct
2 Correct 45 ms 6636 KB Output is correct
3 Partially correct 46 ms 6872 KB Output is partially correct
4 Correct 69 ms 10300 KB Output is correct
5 Correct 72 ms 10852 KB Output is correct
6 Correct 71 ms 10484 KB Output is correct
7 Correct 80 ms 10712 KB Output is correct
8 Correct 70 ms 10516 KB Output is correct
9 Partially correct 46 ms 6860 KB Output is partially correct
10 Correct 85 ms 10376 KB Output is correct
11 Partially correct 69 ms 10168 KB Output is partially correct
12 Partially correct 46 ms 6752 KB Output is partially correct
13 Correct 55 ms 6868 KB Output is correct
14 Partially correct 49 ms 6952 KB Output is partially correct
15 Partially correct 48 ms 6972 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 44 ms 6640 KB Output is correct
18 Correct 43 ms 6876 KB Output is correct
19 Partially correct 47 ms 6640 KB Output is partially correct
20 Correct 70 ms 10304 KB Output is correct
21 Correct 74 ms 10304 KB Output is correct
22 Correct 74 ms 10304 KB Output is correct