제출 #295460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295460		Kastanda	자동 인형 (IOI18_doll)	C++11	100 / 100	121 ms	13012 KiB

doll

// M
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
const int N = 400005;
int n, m, k, len, ts, need, A[N], L[N], R[N], B[N];
int Solve(int l, int r)
{
	if (!need)
		return -1;
	if (r - l < 2)
	{
		need --;
		return B[l];
	}
	int v = ++ ts;
	R[v] = Solve((l + r) >> 1, r);
	L[v] = Solve(l, (l + r) >> 1);
	return -v;
}

void create_circuit(int _m, vector < int > _A)
{
	m = _m;
	n = (int)_A.size();
	for (int i = 0; i < n; i ++)
		A[i] = _A[i];
	A[n] = 0;

	if (n == 1)
	{
		vector < int > C(m + 1, 0);
		vector < int > X, Y;
		C[0] = A[0];
		C[A[0]] = 0;
		answer(C, X, Y);
		return ;
	}
	
	need = n;
	while ((1 << k) < n)
		k ++;

	vector < pair < int , int > > vec;
	for (int i = (1 << k) - n; i < (1 << k); i ++)
	{
		int ra = 0, a = i;
		for (int j = 0; j < k; j ++)
			ra = (ra << 1) | (a & 1), a >>= 1;
		vec.push_back({ra, i});
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < n; i ++)
		B[vec[i].second] = A[i + 1];

	assert(Solve(0, (1 << k)) == -1);

	vector < int > C(m + 1, -1);
	C[0] = A[0];
	vector < int > X(ts), Y(ts);
	for (int i = 0; i < ts; i ++)
		X[i] = L[i + 1], Y[i] = R[i + 1];

	answer(C, X, Y);
	return ;
}

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