oj.uz

Submission #500287

# Submission time Handle Problem Language Result Execution time Memory
500287 2021-12-30T15:38:27 Z sidon Mechanical Doll (IOI18_doll) C++17
100 / 100
 117 ms 12824 KB 
#include <bits/stdc++.h>
using namespace std;
#include "doll.h"

vector<int> s, x(1<<18), y(1<<18), z(1<<18);
int cnt, v = -1, rt, b, n;

int dfs(int l, int r) {
	if(l >= n) return -1;
	if(r - l < 2) {
		return 1;
	} else {
		int m = (l + r) / 2;
		int u = cnt++;
		y[u] = dfs(l, m);
		x[u] = dfs(m, r);
		return -u-1;
	}
}

void create_circuit(int M, vector<int> A) {
	s.assign(M+1, -1);
	A.push_back(0);
	n = size(A);

	while((1<<b)<n) ++b;
	dfs(0, 1<<b);

	for(int &i : A) {
		int u = 0;
		while(u >= 0) {
			z[u] ^= 1;
			int w = -1-(z[u] ? x[u] : y[u]);
			if(w < 0) {
				(z[u] ? x[u] : y[u]) = i;
				rt = u, u = -1;
			} else u = w;
		}
	}
	x.resize(cnt);
	y.resize(cnt);
	answer(s, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 41 ms 6520 KB Output is correct
3 Correct 39 ms 6848 KB Output is correct
4 Correct 2 ms 3276 KB Output is correct
5 Correct 9 ms 4564 KB Output is correct
6 Correct 60 ms 8728 KB Output is correct
7 Correct 2 ms 3276 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 41 ms 6520 KB Output is correct
3 Correct 39 ms 6848 KB Output is correct
4 Correct 2 ms 3276 KB Output is correct
5 Correct 9 ms 4564 KB Output is correct
6 Correct 60 ms 8728 KB Output is correct
7 Correct 2 ms 3276 KB Output is correct
8 Correct 74 ms 9508 KB Output is correct
9 Correct 76 ms 10008 KB Output is correct
10 Correct 114 ms 12824 KB Output is correct
11 Correct 2 ms 3408 KB Output is correct
12 Correct 2 ms 3276 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 41 ms 6520 KB Output is correct
3 Correct 39 ms 6848 KB Output is correct
4 Correct 2 ms 3276 KB Output is correct
5 Correct 9 ms 4564 KB Output is correct
6 Correct 60 ms 8728 KB Output is correct
7 Correct 2 ms 3276 KB Output is correct
8 Correct 74 ms 9508 KB Output is correct
9 Correct 76 ms 10008 KB Output is correct
10 Correct 114 ms 12824 KB Output is correct
11 Correct 2 ms 3408 KB Output is correct
12 Correct 2 ms 3276 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct
14 Correct 112 ms 12400 KB Output is correct
15 Correct 71 ms 8932 KB Output is correct
16 Correct 110 ms 12184 KB Output is correct
17 Correct 2 ms 3280 KB Output is correct
18 Correct 2 ms 3276 KB Output is correct
19 Correct 2 ms 3276 KB Output is correct
20 Correct 112 ms 12684 KB Output is correct
21 Correct 2 ms 3280 KB Output is correct
22 Correct 2 ms 3276 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 72 ms 7044 KB Output is correct
3 Correct 68 ms 7096 KB Output is correct
4 Correct 101 ms 9128 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3276 KB Output is correct
2 Correct 72 ms 7044 KB Output is correct
3 Correct 68 ms 7096 KB Output is correct
4 Correct 101 ms 9128 KB Output is correct
5 Correct 107 ms 10472 KB Output is correct
6 Correct 117 ms 10224 KB Output is correct
7 Correct 108 ms 10304 KB Output is correct
8 Correct 106 ms 9928 KB Output is correct
9 Correct 66 ms 7112 KB Output is correct
10 Correct 104 ms 9892 KB Output is correct
11 Correct 104 ms 9500 KB Output is correct
12 Correct 67 ms 7356 KB Output is correct
13 Correct 71 ms 7672 KB Output is correct
14 Correct 69 ms 7824 KB Output is correct
15 Correct 71 ms 7960 KB Output is correct
16 Correct 3 ms 3532 KB Output is correct
17 Correct 63 ms 7360 KB Output is correct
18 Correct 68 ms 7308 KB Output is correct
19 Correct 69 ms 7352 KB Output is correct
20 Correct 109 ms 9756 KB Output is correct
21 Correct 101 ms 9432 KB Output is correct
22 Correct 104 ms 9548 KB Output is correct