Submission #440111

#	Time	Username	Problem	Language	Result	Execution time	Memory
440111		rainboy	Mechanical Doll (IOI18_doll)	C++11	49 / 100	110 ms	13072 KiB

doll

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

using namespace std;

typedef vector<int> vi;

const int M = 100000, 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;

int build(int *aa, int n) {
	static int k;
	int idx = k++;

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

int kk[M + 1], aa[N_];

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

	for (i = 0; i < n; i++)
		kk[aa_[i]]++;
	for (j = 0; j <= m; j++)
		cc[j] = -1;
	cc[0] = aa_[0];
	n1 = 0;
	for (i = 0; i < n; i++)
		if (kk[aa_[i]] > 1)
			aa_[n1++] = i == n - 1 ? 0 : aa_[i + 1];
		else
			cc[aa_[i]] = i == n - 1 ? 0 : aa_[i + 1];
	if (n1 != 0) {
		n_ = 1;
		while (n_ < n1)
			n_ <<= 1;
		for (i = 0; i < n_ - n1; i++)
			aa[i] = -1;
		for (i = 0; i < n1; i++)
			aa[n_ - n1 + i] = aa_[i];
		xx.resize(n_ - 1), yy.resize(n_ - 1);
		build(aa, n_);
	} else
		for (j = 0; j <= m; j++)
			if (cc[j] == -1)
				cc[j] = 0;
	answer(cc, xx, yy);
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56