Submission #131167

#	Time	Username	Problem	Language	Result	Execution time	Memory
131167		MetB	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 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)
{
	if (n < tl) return origin;

	Node* a = new Node ();

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

	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 == origin) return false;
	else if (to -> l == NULL) to -> x = x;
	else return place_next (to, x);

	return true;
}

void dfs_output (Node* t)
{
	if (t -> x >= 0) return;

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

	dfs_output (t -> l);
	dfs_output (t -> r);
}

void create_circuit (int M, vector <int> A)
{
	origin = new Node ();
	int n = A.size ();

	int start = 1;

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

	root = dfs_init (n, 1, start);

	int p = 0;

	while (p != n)
		if (place_next (root, A[p])) p++;

	dfs_output (root);

	vector <int> C;

	C.push_back (root -> x);

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

	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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56