oj.uz

Submission #131875

# Submission time Handle Problem Language Result Execution time Memory
131875 2019-07-17T20:58:22 Z MetB Mechanical Doll (IOI18_doll) C++14
100 / 100
 290 ms 22784 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, 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 ();

	A.push_back (0);
	int n = (int) A.size ();

	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++;
	}

	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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 60 ms 8392 KB Output is correct
3 Correct 68 ms 8232 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 103 ms 12172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 60 ms 8392 KB Output is correct
3 Correct 68 ms 8232 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 103 ms 12172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 143 ms 15004 KB Output is correct
9 Correct 151 ms 15336 KB Output is correct
10 Correct 290 ms 22532 KB Output is correct
11 Correct 16 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 60 ms 8392 KB Output is correct
3 Correct 68 ms 8232 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1604 KB Output is correct
6 Correct 103 ms 12172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 143 ms 15004 KB Output is correct
9 Correct 151 ms 15336 KB Output is correct
10 Correct 290 ms 22532 KB Output is correct
11 Correct 16 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 232 ms 22144 KB Output is correct
15 Correct 124 ms 15400 KB Output is correct
16 Correct 228 ms 22784 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 222 ms 22272 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 146 ms 13548 KB Output is correct
3 Correct 162 ms 13612 KB Output is correct
4 Correct 237 ms 20664 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 146 ms 13548 KB Output is correct
3 Correct 162 ms 13612 KB Output is correct
4 Correct 237 ms 20664 KB Output is correct
5 Correct 290 ms 22600 KB Output is correct
6 Correct 200 ms 21228 KB Output is correct
7 Correct 215 ms 21340 KB Output is correct
8 Correct 215 ms 21980 KB Output is correct
9 Correct 130 ms 13676 KB Output is correct
10 Correct 252 ms 20912 KB Output is correct
11 Correct 234 ms 20648 KB Output is correct
12 Correct 155 ms 13676 KB Output is correct
13 Correct 131 ms 14884 KB Output is correct
14 Correct 133 ms 14052 KB Output is correct
15 Correct 119 ms 14128 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 113 ms 14908 KB Output is correct
18 Correct 110 ms 13556 KB Output is correct
19 Correct 135 ms 13680 KB Output is correct
20 Correct 247 ms 21780 KB Output is correct
21 Correct 208 ms 20664 KB Output is correct
22 Correct 223 ms 20664 KB Output is correct