oj.uz

Submission #467548

# Submission time Handle Problem Language Result Execution time Memory
467548 2021-08-23T14:50:04 Z LucaDantas Mechanical Doll (IOI18_doll) C++17
100 / 100
 149 ms 14032 KB 
#include "doll.h"
#include <algorithm>
#include <cstdio>

constexpr int inf = 0x3f3f3f3f;

int x[400010], y[400010], state[400010], cnt = 1, fim, pos[400010];

void solve(int id, int pot, int N) {
	if(N == 1 && pot == 0) return (void)(x[id] = -1, y[id] = inf);
	if(N == 2 && pot == 0) return (void)(x[id] = inf, y[id] = inf);
	
	if(N > (1 << pot)) {
		x[id] = -(++cnt);
		int aq = N - (1 << pot);
		solve(-x[id], pot-1, aq);
	} else x[id] = -1;

	y[id] = -(++cnt);
	solve(-y[id], pot-1, std::min(N, 1<<pot));
}

std::vector<int> a;

void go(int u) {
	if(fim == (int)(a.size())) return;
	int& vai = state[u] ? y[u] : x[u];
	state[u] ^= 1;
	if(vai == -1) return go(1);
	if(vai == inf) return (void)(vai = a[fim++], go(1));
	go(-vai);
}

void create_circuit(int M, std::vector<int> A) {
	int N = (int)(A.size());
	if(N == 1) return answer({1, 0}, {}, {});
	
	std::vector<int> C(M + 1);
	C[0] = A[0];

	A.push_back(0);
	A.erase(A.begin());
	a = A;

	for(int i = 1; i <= M; ++i)
		C[i] = -1;
	
	solve(1, 31-__builtin_clz(N)-(__builtin_popcount(N) == 1), N);
	
	std::vector<int> X(cnt), Y(cnt);
	for(int i = 1; i <= cnt; i++)
		X[i-1] = x[i], Y[i-1] = y[i];

	go(1);

	for(int i = 1; i <= cnt; i++)
		X[i-1] = x[i], Y[i-1] = y[i];
	
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 52 ms 4592 KB Output is correct
3 Correct 49 ms 4580 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 72 ms 6928 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 52 ms 4592 KB Output is correct
3 Correct 49 ms 4580 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 72 ms 6928 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 90 ms 9192 KB Output is correct
9 Correct 92 ms 9616 KB Output is correct
10 Correct 142 ms 14032 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 52 ms 4592 KB Output is correct
3 Correct 49 ms 4580 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 72 ms 6928 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 90 ms 9192 KB Output is correct
9 Correct 92 ms 9616 KB Output is correct
10 Correct 142 ms 14032 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 137 ms 13684 KB Output is correct
15 Correct 89 ms 8984 KB Output is correct
16 Correct 132 ms 13516 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 141 ms 13912 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 82 ms 7100 KB Output is correct
3 Correct 82 ms 7068 KB Output is correct
4 Correct 128 ms 10784 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 82 ms 7100 KB Output is correct
3 Correct 82 ms 7068 KB Output is correct
4 Correct 128 ms 10784 KB Output is correct
5 Correct 149 ms 11904 KB Output is correct
6 Correct 135 ms 13300 KB Output is correct
7 Correct 135 ms 13468 KB Output is correct
8 Correct 138 ms 12988 KB Output is correct
9 Correct 81 ms 7948 KB Output is correct
10 Correct 137 ms 12896 KB Output is correct
11 Correct 131 ms 12620 KB Output is correct
12 Correct 84 ms 8208 KB Output is correct
13 Correct 84 ms 8724 KB Output is correct
14 Correct 94 ms 8760 KB Output is correct
15 Correct 85 ms 8912 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 83 ms 8292 KB Output is correct
18 Correct 87 ms 8168 KB Output is correct
19 Correct 86 ms 8276 KB Output is correct
20 Correct 133 ms 12796 KB Output is correct
21 Correct 149 ms 12488 KB Output is correct
22 Correct 138 ms 12604 KB Output is correct