oj.uz

Submission #75914

# Submission time Handle Problem Language Result Execution time Memory
75914 2018-09-11T14:38:44 Z ainta Mechanical Doll (IOI18_doll) C++17
53 / 100
 160 ms 21488 KB 
#include "doll.h"
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 101000
using namespace std;

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

int RR[N_ * 10][2], vv[N_*10], Num[N_*10], ReNum[N_*10];

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;
	}
	

	for (i = 0; i < sz; i++) {
		int t = 0;
		for (j = 0; j < cc; j++) {
			t = t * 2 + ((i >> j) & 1);
		}
		int nxt;
		if (t < sz - L) {
			nxt = ret;
		}
		if (t >= sz - L) {
			nxt = -TP[t - (sz - L)];
		}
		RR[cnt + sz / 2 + (i >> 1)][i & 1] = nxt;
	}

	for (i = cnt + sz - 1; i >= ret; i--) {
		int x = i - cnt;
		if (RR[i][0] >= 0 && RR[i][1] >= 0 && RR[i][0] == ret && RR[i][1] == ret) {
			RR[cnt + x / 2][x & 1] = ret;
			vv[i] = 1;
		}
	}

	cnt += sz - 1;



	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();
		}
	}
	int ct = 0;
	for (i = 1; i <= cnt; i++) {
		if (!vv[i]) {
			Num[i] = ++ct;
			ReNum[ct] = i;
		}
	}
	vector<int>C(m+1), X(ct), Y(ct);
	for (i = 0; i <= m; i++)C[i] = Out[i];
	for (i = 0; i < ct; i++) {
		int x = RR[ReNum[i + 1]][0];
		int y = RR[ReNum[i + 1]][1];
		if (x > 0)x = Num[x];
		if (y > 0)y = Num[y];
		x = -x, y = -y;
		X[i] = x, Y[i] = y;
	}
	answer(C, X, Y);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 38 ms 6696 KB Output is correct
3 Correct 30 ms 6260 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 61 ms 8048 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 38 ms 6696 KB Output is correct
3 Correct 30 ms 6260 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 61 ms 8048 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 56 ms 9324 KB Output is correct
9 Correct 59 ms 9664 KB Output is correct
10 Correct 102 ms 12788 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 38 ms 6696 KB Output is correct
3 Correct 30 ms 6260 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 14 ms 4172 KB Output is correct
6 Correct 61 ms 8048 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 56 ms 9324 KB Output is correct
9 Correct 59 ms 9664 KB Output is correct
10 Correct 102 ms 12788 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 108 ms 15232 KB Output is correct
15 Correct 78 ms 9068 KB Output is correct
16 Correct 107 ms 12408 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 129 ms 13848 KB Output is correct
21 Correct 3 ms 2636 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 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 3 ms 2636 KB Output is partially correct
2 Correct 61 ms 9980 KB Output is correct
3 Partially correct 83 ms 14944 KB Output is partially correct
4 Partially correct 99 ms 16320 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 2636 KB Output is partially correct
2 Correct 61 ms 9980 KB Output is correct
3 Partially correct 83 ms 14944 KB Output is partially correct
4 Partially correct 99 ms 16320 KB Output is partially correct
5 Partially correct 134 ms 17972 KB Output is partially correct
6 Partially correct 160 ms 19572 KB Output is partially correct
7 Partially correct 128 ms 19048 KB Output is partially correct
8 Partially correct 141 ms 20600 KB Output is partially correct
9 Partially correct 90 ms 14740 KB Output is partially correct
10 Partially correct 129 ms 20592 KB Output is partially correct
11 Partially correct 126 ms 21488 KB Output is partially correct
12 Partially correct 84 ms 15064 KB Output is partially correct
13 Partially correct 84 ms 13808 KB Output is partially correct
14 Partially correct 85 ms 13368 KB Output is partially correct
15 Partially correct 86 ms 12740 KB Output is partially correct
16 Partially correct 5 ms 2968 KB Output is partially correct
17 Partially correct 97 ms 12396 KB Output is partially correct
18 Partially correct 71 ms 12484 KB Output is partially correct
19 Partially correct 74 ms 13224 KB Output is partially correct
20 Partially correct 100 ms 16104 KB Output is partially correct
21 Partially correct 123 ms 19084 KB Output is partially correct
22 Partially correct 109 ms 15300 KB Output is partially correct