Submission #75926

#	Time	Username	Problem	Language	Result	Execution time	Memory
75926		ainta	Mechanical Doll (IOI18_doll)	C++17	100 / 100	141 ms	20560 KiB

doll

#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;
	A.push_back(0);
	for (i = 0; i < n; i++) {
		E[A[i]].push_back(A[i + 1]);
	}
	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];
	}
	for (i = 0; i < n; i++) {
		if (E[A[i]].size() >= 2) {
			TP.push_back(A[i + 1]);
		}
	}
	int rt = Make();
	for (i = 0; i <= M; i++)if (E[i].size() >= 2)Out[i] = rt;
	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];
		if (C[i] < 0)C[i] = -Num[-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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56