제출 #440101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440101		rainboy	자동 인형 (IOI18_doll)	C++17	0 / 100	13 ms	3456 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 idx;

	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], 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_);
	}
	answer(cc, xx, yy);
}

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