oj.uz

Submission #75008

# Submission time Handle Problem Language Result Execution time Memory
75008 2018-09-08T03:17:42 Z ainta Mechanical Doll (IOI18_doll) C++17
53 / 100
 166 ms 20808 KB 
#include "doll.h"
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 201000
using namespace std;

int n, m, Out[N_], cnt, chk[N_*10], PV;

int RR[N_ * 10][2];

vector<int>E[N_], TP;

void Go(int a, int L, int cur, int ed) {
	if (L == 1) {
		if (RR[a][cur & 1]) {
			RR[RR[a][cur & 1]][0] = ed;
			return;
		}
		RR[a][cur & 1] = ed;
		return;
	}
	if (!RR[a][cur & 1])RR[a][cur & 1] = ++cnt;
	Go(RR[a][cur & 1], L - 1, cur >> 1, ed);
}

int Make() {
	int ret = cnt + 1;
	int i, sz = 1, cc = 0, j;
	int L = TP.size();
	while (sz < L) sz *= 2, cc++;
	
	for (i = 1; i < sz/2; i++) {
		RR[cnt + i][0] = cnt + i * 2;
		RR[cnt + i][1] = cnt + i * 2 + 1;
	}
	cnt += sz - 1;


	for (i = 0; i < L; i++) {
		Go(ret, cc, sz - L + i, -TP[i]);
	}
	for (i = ret; i <= cnt; i++) {
		if (!RR[i][0])RR[i][0] = ret;
	}


	return -ret;
}

void create_circuit(int M, std::vector<int> A) {
	n = A.size();
	m = M;
	E[0].push_back(A[0]);
	int i;
	for (i = 0; i < n - 1; i++) {
		E[A[i]].push_back(A[i + 1]);
	}
	E[A[n - 1]].push_back(0);
	for (i = 0; i <= M; i++) {
		if (E[i].size() == 0) Out[i] = 0;
		else if (E[i].size() == 1)Out[i] = E[i][0];
		else {
			TP = E[i];
			Out[i] = Make();
		}
	}
	vector<int>C(m+1), X(cnt), Y(cnt);
	for (i = 0; i <= m; i++)C[i] = Out[i];
	for (i = 0; i < cnt; i++)X[i] = -RR[i+1][0], Y[i] = -RR[i+1][1];
	answer(C, X, Y);

}

Compilation message

doll.cpp: In function 'int Make()':
doll.cpp:29:25: warning: unused variable 'j' [-Wunused-variable]
   29 |  int i, sz = 1, cc = 0, j;
      |                         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 44 ms 9116 KB Output is correct
3 Correct 45 ms 8596 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 20 ms 6476 KB Output is correct
6 Correct 47 ms 10436 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 44 ms 9116 KB Output is correct
3 Correct 45 ms 8596 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 20 ms 6476 KB Output is correct
6 Correct 47 ms 10436 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 61 ms 11120 KB Output is correct
9 Correct 68 ms 11588 KB Output is correct
10 Correct 102 ms 14368 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 44 ms 9116 KB Output is correct
3 Correct 45 ms 8596 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 20 ms 6476 KB Output is correct
6 Correct 47 ms 10436 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 61 ms 11120 KB Output is correct
9 Correct 68 ms 11588 KB Output is correct
10 Correct 102 ms 14368 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 115 ms 15888 KB Output is correct
15 Correct 66 ms 10572 KB Output is correct
16 Correct 107 ms 13596 KB Output is correct
17 Correct 5 ms 4968 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 4940 KB Output is correct
20 Correct 118 ms 15024 KB Output is correct
21 Correct 6 ms 4960 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4940 KB Output is partially correct
2 Correct 77 ms 11272 KB Output is correct
3 Partially correct 95 ms 15276 KB Output is partially correct
4 Partially correct 137 ms 16392 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4940 KB Output is partially correct
2 Correct 77 ms 11272 KB Output is correct
3 Partially correct 95 ms 15276 KB Output is partially correct
4 Partially correct 137 ms 16392 KB Output is partially correct
5 Partially correct 166 ms 18196 KB Output is partially correct
6 Partially correct 164 ms 19360 KB Output is partially correct
7 Partially correct 127 ms 18984 KB Output is partially correct
8 Partially correct 145 ms 20000 KB Output is partially correct
9 Partially correct 94 ms 15008 KB Output is partially correct
10 Partially correct 156 ms 19956 KB Output is partially correct
11 Partially correct 134 ms 20808 KB Output is partially correct
12 Partially correct 104 ms 15448 KB Output is partially correct
13 Partially correct 93 ms 14468 KB Output is partially correct
14 Partially correct 83 ms 14156 KB Output is partially correct
15 Partially correct 78 ms 13668 KB Output is partially correct
16 Partially correct 7 ms 5296 KB Output is partially correct
17 Partially correct 77 ms 13200 KB Output is partially correct
18 Partially correct 77 ms 13204 KB Output is partially correct
19 Partially correct 80 ms 13844 KB Output is partially correct
20 Partially correct 100 ms 16288 KB Output is partially correct
21 Partially correct 130 ms 18756 KB Output is partially correct
22 Partially correct 113 ms 15688 KB Output is partially correct