Submission #1059834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059834		jerzyk	Mechanical Doll (IOI18_doll)	C++17	100 / 100	89 ms	23800 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int L, lft;
int tab[N];
int l[N], r[N], num[N], cnt = 0;
vector<pair<int, int>> pos;
vector<int> AX, AY;

void Rem(int v, int siz)
{
	if(lft == 0 || siz == 1) return;
	if(siz / 2 <= lft)
	{
		l[v] = -1;
		lft -= siz / 2;
	}
	if(l[v] != -1)
		Rem(v * 2, siz / 2);
	else
		Rem(v * 2 + 1, siz / 2);
}

void FindPos(int v, int num, int wys)
{
	if(v >= L)
	{
		pos.pb(make_pair(num, v));
		return;
	}
	if(l[v] != -1)
		FindPos(v * 2, num, wys + 1);
	FindPos(v * 2 + 1, num + (1<<wys), wys + 1);
}

void Fin(int v)
{
	--cnt; num[v] = cnt;
	if(l[v] == 0 && v * 2 < L)
	{
		Fin(v * 2);
		l[v] = num[v * 2];
	}
	if(r[v] == 0 && v * 2 < L)
	{
		Fin(v * 2 + 1);
		r[v] = num[v * 2 + 1];
	}
}

void DoOut(int v)
{
	//cerr << v << " " << l[v] << " " << r[v] << "\n";
	AX.pb(l[v]); AY.pb(r[v]);
	if(l[v] < -1)
		DoOut(v * 2);
	if(r[v] < -1)
		DoOut(v * 2 + 1);
}

void DoB(int n)
{
	L = 2;
	while(L < n)
		L *= 2;
	lft = L - n;
	Rem(1, L);
	FindPos(1, 0, 0);
	sort(pos.begin(), pos.end());
	for(int i = 1; i <= n; ++i)
	{
		int o = pos[i - 1].nd / 2;
		if(pos[i - 1].nd % 2 == 0)
			l[o] = tab[i];
		else
			r[o] = tab[i];
	}
	Fin(1);
	DoOut(1);
}

void create_circuit(int M, vector<int> A)
{
	int n = A.size();
	vector<int> C, X, Y;
	for(int i = 1; i < n; ++i)
		tab[i] = A[i];
	C.pb(A[0]);
	for(int i = 1; i <= M; ++i)
		C.pb(-1);
	DoB(n);
	//cerr << "exit " << AX.size() << " " << AY.size() << "\n";
	answer(C, AX, AY);
}

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