Submission #131866

#	Time	Username	Problem	Language	Result	Execution time	Memory
131866		MetB	Mechanical Doll (IOI18_doll)	C++14	100 / 100	284 ms	21808 KiB

doll

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
typedef long long ll;
typedef long double ld;
 
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
 
using namespace std;

int n, m, a[1000000], ptr, x[1000000], y[1000000];

void answer (vector <int> C, vector <int> X, vector <int> Y);

struct Node
{
	int x;
	bool on;

	Node *l, *r;

	Node () : x (0), on (false), l (NULL), r (NULL) {}
};

Node *root, *origin;

Node* dfs_init (int n, int tl, int tr, bool rt)
{
	if (tr <= n) return root;

	Node* a = new Node ();

	if (rt) root = a;

	if (tl != tr)
	{
		a -> x = -(++ptr);
		a -> l = dfs_init (n, tl, (tl + tr) / 2, false);
		a -> r = dfs_init (n, (tl + tr) / 2 + 1, tr, false);
	}

	return a;
}

bool place_next (Node* t, int x)
{
	t -> on = !(t -> on);

	Node* to = new Node ();

	if (t -> on) to = t -> l;
	else to = t -> r;

	if (to == root) return false;
	else if (!to -> l) to -> x = x;
	else return place_next (to, x);

	return true;
}

void dfs_output (Node* t)
{
	if (!t -> l) return;

	x[-(t -> x) - 1] = t -> l -> x;
	y[-(t -> x) - 1] = t -> r -> x;

	if (t -> l != root) dfs_output (t -> l);
	if (t -> r != root) dfs_output (t -> r);
}

void create_circuit (int m, vector <int> A)
{
	origin = new Node ();

	int n = (int) A.size ();
	int n_ = n + 1;

	int start = 1, s = 0;

	while (start < n_) start <<= 1;

	dfs_init (start - n_, 1, start, true);

	int p = 0;

	while (p < n)
	{
		s++;
		if (place_next (root, A[p])) p++;
	}

	while (!place_next (root, 0));

	dfs_output (root);

	vector <int> C;

	C.push_back (-1);

	for (int i = 0; i < m; i++)
		C.push_back (-1);

	vector <int> X, Y;

	for (int i = 0; i < ptr; i++)
	{
		X.push_back (x[i]);
		Y.push_back (y[i]);
	}

	answer (C, X, Y);
}

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