Submission #75007

#	Time	Username	Problem	Language	Result	Execution time	Memory
75007		ainta	Mechanical Doll (IOI18_doll)	C++17	53 / 100	155 ms	19140 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];

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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56