oj.uz

Submission #131170

# Submission time Handle Problem Language Result Execution time Memory
131170 2019-07-16T17:48:20 Z MetB Mechanical Doll (IOI18_doll) C++14
0 / 100
 2 ms 204 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -