oj.uz

Submission #769742

# Submission time Handle Problem Language Result Execution time Memory
769742 2023-06-30T07:33:15 Z SanguineChameleon Mechanical Doll (IOI18_doll) C++17
100 / 100
 58 ms 12180 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	A.push_back(M + 1);
	vector<int> C(M + 1);
	C[0] = A[0];
	if (N == 1) {
		C[A[0]] = 0;
		answer(C, vector<int>(), vector<int>());
		return;
	}
	int K = 0;
	while ((1 << K) < N) {
		K++;
	}
	vector<int> X;
	vector<int> Y;
	vector<int> cur_layer(1 << K, M + 1);
	int cnt = 0;
	for (int i = 0; i < (1 << K) - 1; i++) {
		int last = 0;
		for (int j = 0; j < K; j++) {
			last |= ((i >> j) & 1) << (K - 1 - j);
		}
		if (last < ((1 << K) - N)) {
			continue;
		}
		cur_layer[last] = A[++cnt];
	}
	cur_layer[(1 << K) - 1] = 0;
	cnt = 0;
	for (int i = K - 1; i >= 0; i--) {
		vector<int> nxt_layer(1 << i, M + 1);
		for (int j = 0; j < (1 << i); j++) {
			if (cur_layer[j << 1] != M + 1 || cur_layer[j << 1 | 1] != M + 1) {
				cnt++;
				nxt_layer[j] = -cnt;
				X.push_back(cur_layer[j << 1]);
				Y.push_back(cur_layer[j << 1 | 1]);
			}
		}
		cur_layer.swap(nxt_layer);
	}
	for (int i = 1; i <= M; i++) {
		C[i] = cur_layer[0];
	}
	for (int i = 0; i < cnt; i++) {
		if (X[i] == M + 1) {
			X[i] = cur_layer[0];
		}
		if (Y[i] == M + 1) {
			Y[i] = cur_layer[0];
		}
	}
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 24 ms 4760 KB Output is correct
3 Correct 22 ms 4844 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 39 ms 7312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 24 ms 4760 KB Output is correct
3 Correct 22 ms 4844 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 39 ms 7312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 37 ms 7880 KB Output is correct
9 Correct 43 ms 8896 KB Output is correct
10 Correct 58 ms 12180 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 24 ms 4760 KB Output is correct
3 Correct 22 ms 4844 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 39 ms 7312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 37 ms 7880 KB Output is correct
9 Correct 43 ms 8896 KB Output is correct
10 Correct 58 ms 12180 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 57 ms 11756 KB Output is correct
15 Correct 37 ms 7652 KB Output is correct
16 Correct 54 ms 11520 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 56 ms 11900 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 31 ms 6572 KB Output is correct
3 Correct 34 ms 6812 KB Output is correct
4 Correct 48 ms 10132 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 31 ms 6572 KB Output is correct
3 Correct 34 ms 6812 KB Output is correct
4 Correct 48 ms 10132 KB Output is correct
5 Correct 54 ms 11400 KB Output is correct
6 Correct 52 ms 11100 KB Output is correct
7 Correct 55 ms 11236 KB Output is correct
8 Correct 51 ms 10920 KB Output is correct
9 Correct 35 ms 6880 KB Output is correct
10 Correct 56 ms 10884 KB Output is correct
11 Correct 49 ms 10500 KB Output is correct
12 Correct 34 ms 7108 KB Output is correct
13 Correct 34 ms 7204 KB Output is correct
14 Correct 40 ms 7460 KB Output is correct
15 Correct 37 ms 7564 KB Output is correct
16 Correct 2 ms 436 KB Output is correct
17 Correct 35 ms 6760 KB Output is correct
18 Correct 42 ms 6820 KB Output is correct
19 Correct 34 ms 7072 KB Output is correct
20 Correct 50 ms 10784 KB Output is correct
21 Correct 50 ms 10496 KB Output is correct
22 Correct 49 ms 10620 KB Output is correct