Submission #440117

#	Time	Username	Problem	Language	Result	Execution time	Memory
440117		rainboy	자동 인형 (IOI18_doll)	C++11	53 / 100	126 ms	15388 KiB

doll

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

using namespace std;

typedef vector<int> vi;

const int N = 200000, 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(N * 2), yy(N * 2); int k;

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

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

int kk[M + 1], iii[M + 1][3], aa[N_], aa1[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++)
		if (kk[aa_[i]] <= 2)
			iii[aa_[i]][kk[aa_[i]]++] = i;
	n1 = 0;
	for (i = 0; i < n; i++)
		if (kk[aa_[i]] > 2)
			aa1[n1++] = 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] = aa1[i];
		build(aa, n_);
		for (j = 0; j <= m; j++)
			cc[j] = -1;
	}
	cc[0] = aa_[0];
	for (j = 0; j <= m; j++)
		if (kk[j] == 1) {
			i = iii[j][0];
			cc[j] = i + 1 == n ? 0 : aa_[i + 1];
		} else if (kk[j] == 2) {
			int u, i1, i2;

			i1 = iii[j][0], i2 = iii[j][1];
			cc[j] = -((u = k++) + 1);
			xx[u] = i1 + 1 == n ? 0 : aa_[i1 + 1], yy[u] = i2 + 1 == n ? 0 : aa_[i2 + 1];
		}
	xx.resize(k), yy.resize(k);
	answer(cc, xx, yy);
}

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