oj.uz

답안 #131846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131846 2019-07-17T19:44:11 Z MetB 자동 인형 (IOI18_doll) C++14
37 / 100
 325 ms 26884 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)
{
	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 (n_, 1, start, true);

	int p = 0;

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

	for (int i = s; i < start - 1; i++)
		place_next (root, -1);

	place_next (root, 0);

	dfs_output (root);

	vector <int> C;

	C.push_back (root -> x);

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 261 ms 26092 KB Output is partially correct
3 Partially correct 279 ms 26096 KB Output is partially correct
4 Partially correct 278 ms 26592 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 261 ms 26092 KB Output is partially correct
3 Partially correct 279 ms 26096 KB Output is partially correct
4 Partially correct 278 ms 26592 KB Output is partially correct
5 Partially correct 325 ms 26884 KB Output is partially correct
6 Partially correct 310 ms 26712 KB Output is partially correct
7 Partially correct 273 ms 26844 KB Output is partially correct
8 Partially correct 282 ms 26764 KB Output is partially correct
9 Partially correct 254 ms 26100 KB Output is partially correct
10 Partially correct 274 ms 26704 KB Output is partially correct
11 Partially correct 273 ms 26608 KB Output is partially correct
12 Partially correct 249 ms 26076 KB Output is partially correct
13 Partially correct 302 ms 26132 KB Output is partially correct
14 Partially correct 257 ms 26160 KB Output is partially correct
15 Partially correct 258 ms 26288 KB Output is partially correct
16 Partially correct 5 ms 1100 KB Output is partially correct
17 Correct 107 ms 13688 KB Output is correct
18 Partially correct 296 ms 26040 KB Output is partially correct
19 Partially correct 256 ms 26092 KB Output is partially correct
20 Partially correct 319 ms 26608 KB Output is partially correct
21 Partially correct 314 ms 26632 KB Output is partially correct
22 Partially correct 322 ms 26576 KB Output is partially correct