oj.uz

답안 #75916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75916 2018-09-11T14:43:19 Z ainta 자동 인형 (IOI18_doll) C++17
34 / 100
 137 ms 18056 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;
	}
	

	int ccc = 0;

	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[ccc++];
		}
		RR[cnt + sz / 2 + (t >> 1)][t & 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 32 ms 6748 KB Output is correct
3 Correct 35 ms 6256 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 66 ms 8056 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 32 ms 6748 KB Output is correct
3 Correct 35 ms 6256 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 66 ms 8056 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 65 ms 9328 KB Output is correct
9 Correct 83 ms 9712 KB Output is correct
10 Correct 114 ms 12792 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 32 ms 6748 KB Output is correct
3 Correct 35 ms 6256 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 66 ms 8056 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 65 ms 9328 KB Output is correct
9 Correct 83 ms 9712 KB Output is correct
10 Correct 114 ms 12792 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 128 ms 15184 KB Output is correct
15 Correct 60 ms 9068 KB Output is correct
16 Correct 106 ms 12392 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 137 ms 13808 KB Output is correct
21 Correct 3 ms 2632 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2636 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 50 ms 9960 KB Output is correct
3 Correct 60 ms 12060 KB Output is correct
4 Correct 84 ms 14488 KB Output is correct

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 50 ms 9960 KB Output is correct
3 Correct 60 ms 12060 KB Output is correct
4 Correct 84 ms 14488 KB Output is correct
5 Incorrect 136 ms 18056 KB wrong serial number
6 Halted 0 ms 0 KB -