Submission #440083

#	Time	Username	Problem	Language	Result	Execution time	Memory
440083		rainboy	Mechanical Doll (IOI18_doll)	C++11	37 / 100	108 ms	12332 KiB

doll

#include "doll.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 200000, N_ = 1 << 18;	/* N_ = pow2(ceil(log2(N))) */

int tmp[N_];

void split(int *aa, int n) {
	int i, j, k;

	for (i = 0, j = n / 2, k = 0; k < n; k++)
		tmp[k % 2 == 0 ? i++ : j++] = aa[k];
	memcpy(aa, tmp, n * sizeof *tmp);
}

vi xx, yy;

void build(int *aa, int n, int idx) {
	if (n == 2)
		xx[idx] = aa[0], yy[idx] = aa[1];
	else {
		split(aa, n);
		xx[idx] = -(idx * 2 + 1 + 1), yy[idx] = -(idx * 2 + 2 + 1);
		build(aa, n / 2, idx * 2 + 1), build(aa + n / 2, n / 2, idx * 2 + 2);
	}
}

int aa[N_];

void create_circuit(int m, vi aa_) {
	vi cc(m + 1);
	int n = aa_.size(), n_, i;

	n_ = 1;
	while (n_ < n + 1)
		n_ <<= 1;
	for (i = 0; i < n_ - (n + 1); i++)
		aa[i] = -1;
	for (i = 0; i < n; i++)
		aa[n_ - (n + 1) + i] = aa_[i];
	xx.resize(n_ - 1), yy.resize(n_ - 1);
	build(aa, n_, 0);
	for (i = 0; i <= m; i++)
		cc[i] = -1;
	answer(cc, xx, yy);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56