oj.uz

Submission #541976

# Submission time Handle Problem Language Result Execution time Memory
541976 2022-03-24T23:31:11 Z sliviu Mechanical Doll (IOI18_doll) C++17
100 / 100
 126 ms 12256 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

void create_circuit(int m, vector<int> a) {
	int n = a.size(), p = 1, k = 1;
	if (a.size() & 1)
		a.emplace_back(-1);
	a.emplace_back(0);
	vector<int> c(m + 1, -1), x(400001), y(400001), parity(400001);
	while (p < n)
		p *= 2;
	function<int(int, int)> Build = [&](int left, int right) {
		if (left == right)
			return 0;
		if (right < p - n)
			return -1;
		int m = (left + right) / 2, cur = k++;
		x[cur - 1] = Build(left, m), y[cur - 1] = Build(m + 1, right);
		return -cur;
	};
	Build(0, p - 1);
	for (int i = 1; i <= n; ++i) {
		int cur = -1;
		while (cur) {
			int& next = !parity[-cur - 1] ? x[-cur - 1] : y[-cur - 1];
			parity[-cur - 1] ^= 1;
			cur = next;
			if (!next)
				next = a[i];
		}
	}
	c[0] = a[0];
	x.resize(k), y.resize(k);
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 44 ms 7972 KB Output is correct
3 Correct 42 ms 7376 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 10 ms 6100 KB Output is correct
6 Correct 63 ms 8652 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 44 ms 7972 KB Output is correct
3 Correct 42 ms 7376 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 10 ms 6100 KB Output is correct
6 Correct 63 ms 8652 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 76 ms 9884 KB Output is correct
9 Correct 88 ms 10168 KB Output is correct
10 Correct 122 ms 12256 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 44 ms 7972 KB Output is correct
3 Correct 42 ms 7376 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 10 ms 6100 KB Output is correct
6 Correct 63 ms 8652 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 76 ms 9884 KB Output is correct
9 Correct 88 ms 10168 KB Output is correct
10 Correct 122 ms 12256 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 123 ms 11864 KB Output is correct
15 Correct 81 ms 9288 KB Output is correct
16 Correct 115 ms 11672 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 118 ms 12092 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4908 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4908 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 72 ms 8324 KB Output is correct
3 Correct 74 ms 8324 KB Output is correct
4 Correct 115 ms 9820 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 72 ms 8324 KB Output is correct
3 Correct 74 ms 8324 KB Output is correct
4 Correct 115 ms 9820 KB Output is correct
5 Correct 119 ms 10308 KB Output is correct
6 Correct 116 ms 10124 KB Output is correct
7 Correct 116 ms 10148 KB Output is correct
8 Correct 112 ms 10008 KB Output is correct
9 Correct 75 ms 8332 KB Output is correct
10 Correct 114 ms 9912 KB Output is correct
11 Correct 112 ms 9892 KB Output is correct
12 Correct 75 ms 8340 KB Output is correct
13 Correct 74 ms 8544 KB Output is correct
14 Correct 76 ms 8548 KB Output is correct
15 Correct 77 ms 8520 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 72 ms 8212 KB Output is correct
18 Correct 73 ms 8236 KB Output is correct
19 Correct 76 ms 8264 KB Output is correct
20 Correct 126 ms 9896 KB Output is correct
21 Correct 112 ms 9920 KB Output is correct
22 Correct 118 ms 9896 KB Output is correct