oj.uz

Submission #769076

# Submission time Handle Problem Language Result Execution time Memory
769076 2023-06-29T06:54:22 Z SanguineChameleon Mechanical Doll (IOI18_doll) C++17
49 / 100
 71 ms 10332 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> A, C, X, Y, cnt;
int N, M, K;

void build(int id, int depth, int cur) {
	if (depth == K - 1) {
		X[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
		cur += 1 << depth;
		Y[id - 1] = (cur < N - 1 ? A[cur + 1] : (cur == ((1 << K) - 1) ? 0 : -1));
		return;
	}
	X[id - 1] = -(id * 2);
	Y[id - 1] = -(id * 2 + 1);
	build(id * 2, depth + 1, cur);
	build(id * 2 + 1, depth + 1, cur + (1 << depth));
}

void create_circuit(int _M, vector<int> _A) {
	A = _A;
	N = A.size();
	M = _M;
	cnt.resize(M + 1);
	for (int i = 0; i < N; i++) {
		cnt[A[i]]++;
	}
	bool sub3 = true;
	for (int i = 1; i <= M; i++) {
		if (cnt[i] > 1) {
			sub3 = false;
			break;
		}
	}
	if (sub3) {
		C.resize(M + 1);
		C[0] = A[0];
		for (int i = 0; i < N; i++) {
			if (cnt[A[i]] == 1) {
				C[A[i]] = (i + 1 < N ? A[i + 1] : 0);
			}
		}
		answer(C, X, Y);
		return;
	}
	K = 0;
	while ((1 << K) < N) {
		K++;
	}
	C.resize(M + 1, -1);
	C[0] = A[0];
	if (K == 0) {
		answer(C, X, Y);
		return;
	}
	X.resize((1 << K) - 1);
	Y.resize((1 << K) - 1);
	build(1, 0, 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 14 ms 2900 KB Output is correct
3 Correct 16 ms 2388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 17 ms 3264 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 14 ms 2900 KB Output is correct
3 Correct 16 ms 2388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 17 ms 3264 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 35 ms 6404 KB Output is correct
9 Incorrect 55 ms 10332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 14 ms 2900 KB Output is correct
3 Correct 16 ms 2388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 17 ms 3264 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 35 ms 6404 KB Output is correct
9 Incorrect 55 ms 10332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 29 ms 5124 KB Output is correct
3 Partially correct 51 ms 8228 KB Output is partially correct
4 Partially correct 52 ms 8976 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 29 ms 5124 KB Output is correct
3 Partially correct 51 ms 8228 KB Output is partially correct
4 Partially correct 52 ms 8976 KB Output is partially correct
5 Partially correct 56 ms 10052 KB Output is partially correct
6 Partially correct 56 ms 9824 KB Output is partially correct
7 Partially correct 71 ms 10012 KB Output is partially correct
8 Partially correct 54 ms 9640 KB Output is partially correct
9 Partially correct 47 ms 8204 KB Output is partially correct
10 Partially correct 66 ms 9548 KB Output is partially correct
11 Partially correct 56 ms 9164 KB Output is partially correct
12 Partially correct 46 ms 8476 KB Output is partially correct
13 Correct 35 ms 5616 KB Output is correct
14 Partially correct 49 ms 9044 KB Output is partially correct
15 Partially correct 49 ms 9224 KB Output is partially correct
16 Partially correct 2 ms 596 KB Output is partially correct
17 Correct 33 ms 5092 KB Output is correct
18 Correct 33 ms 5088 KB Output is correct
19 Partially correct 47 ms 8516 KB Output is partially correct
20 Partially correct 54 ms 9316 KB Output is partially correct
21 Partially correct 53 ms 9092 KB Output is partially correct
22 Partially correct 52 ms 9164 KB Output is partially correct