oj.uz

Submission #147106

# Submission time Handle Problem Language Result Execution time Memory
147106 2019-08-27T14:00:12 Z dolphingarlic Mechanical Doll (IOI18_doll) C++14
100 / 100
 146 ms 10396 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int N, P = 1, switches = 1;
vector<int> X(1<<19), Y(1<<19);
bool state[1<<19];

int build(int l, int r) {
	if (l >= r) return 0;
	if (r < P - N) return -1;

	int ts = switches++, mid = (l + r) / 2;
	X[ts - 1] = build(l, mid);
	Y[ts - 1] = build(mid + 1, r);
	return -ts;
}

void point(int i, int j) {
	int &a = state[-i] ? Y[-i - 1] : X[-i - 1];
	state[-i] = !state[-i];

	if (!a) a = j;
	else point(a, j);
}

void create_circuit(int M, vector<int> A) {
	N = A.size();
    while (P < N) P *= 2;

	build(0, P - 1);

	for (int i = 1; i < N; i++) point(-1, A[i]);
	if (N & 1) point(-1, -1);
	point(-1, 0);

	X.resize(switches), Y.resize(switches);
	vector<int> C(M + 1, -1);
	C[0] = A[0];

    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 47 ms 7116 KB Output is correct
3 Correct 47 ms 6800 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 13 ms 5580 KB Output is correct
6 Correct 72 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 47 ms 7116 KB Output is correct
3 Correct 47 ms 6800 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 13 ms 5580 KB Output is correct
6 Correct 72 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 87 ms 8380 KB Output is correct
9 Correct 98 ms 8764 KB Output is correct
10 Correct 140 ms 10396 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 4 ms 4300 KB Output is correct
13 Correct 3 ms 4324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 47 ms 7116 KB Output is correct
3 Correct 47 ms 6800 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 13 ms 5580 KB Output is correct
6 Correct 72 ms 8004 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 87 ms 8380 KB Output is correct
9 Correct 98 ms 8764 KB Output is correct
10 Correct 140 ms 10396 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 4 ms 4300 KB Output is correct
13 Correct 3 ms 4324 KB Output is correct
14 Correct 133 ms 10056 KB Output is correct
15 Correct 85 ms 8004 KB Output is correct
16 Correct 137 ms 9928 KB Output is correct
17 Correct 3 ms 4300 KB Output is correct
18 Correct 3 ms 4300 KB Output is correct
19 Correct 3 ms 4300 KB Output is correct
20 Correct 134 ms 10140 KB Output is correct
21 Correct 4 ms 4300 KB Output is correct
22 Correct 4 ms 4300 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4300 KB Output is correct
2 Correct 75 ms 7604 KB Output is correct
3 Correct 80 ms 7612 KB Output is correct
4 Correct 139 ms 9288 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4300 KB Output is correct
2 Correct 75 ms 7604 KB Output is correct
3 Correct 80 ms 7612 KB Output is correct
4 Correct 139 ms 9288 KB Output is correct
5 Correct 132 ms 9804 KB Output is correct
6 Correct 128 ms 9832 KB Output is correct
7 Correct 125 ms 9908 KB Output is correct
8 Correct 123 ms 9576 KB Output is correct
9 Correct 95 ms 7608 KB Output is correct
10 Correct 126 ms 9476 KB Output is correct
11 Correct 127 ms 9236 KB Output is correct
12 Correct 83 ms 7612 KB Output is correct
13 Correct 84 ms 7924 KB Output is correct
14 Correct 86 ms 7992 KB Output is correct
15 Correct 86 ms 8064 KB Output is correct
16 Correct 6 ms 4428 KB Output is correct
17 Correct 79 ms 7624 KB Output is correct
18 Correct 77 ms 7620 KB Output is correct
19 Correct 111 ms 7604 KB Output is correct
20 Correct 131 ms 9416 KB Output is correct
21 Correct 146 ms 9240 KB Output is correct
22 Correct 123 ms 9288 KB Output is correct