oj.uz

Submission #1068506

# Submission time Handle Problem Language Result Execution time Memory
1068506 2024-08-21T10:20:54 Z Joshua_Andersson Mechanical Doll (IOI18_doll) C++14
37 / 100
 115 ms 11528 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

map<int,int> ind;
vi state;
vi x, y;
int k=0;
void build_tree(int u, int d, vi& x, vi& y)
{
	if (d==0)
	{
		x[u] = inf;
		y[u] = inf;
		return;
	}
	x[u] = u * 2;
	y[u] = u * 2 + 1;
	build_tree(u * 2, d - 1, x, y);
	build_tree(u * 2+1, d - 1, x, y);
}

void traverse(int u, int t)
{
	int& v = state[u]?y[u]:x[u];
	state[u] ^= 1;
	if (v==inf)
	{
		v = t;
		return;
	}
	traverse(v, t);
}

void create_circuit(int m, std::vector<int> a)
{
	int n = sz(a);
	while ((1<<(k+1))<=n)
	{
		k++;
	}
	vi c(m + 1, -1);

	state.resize(1 << (k+1));
	x.resize(1 << (k+1), inf);
	y.resize(1 << (k+1), inf);
	build_tree(1, k, x, y);
	rep(i, n)
	{
		traverse(1, a[i]);
	}
	repp(i, n, (1 << (k+1))-1)
	{
		traverse(1, -1);
	}
	traverse(1, 0);
	rep(i, 1 << k) x[i] *= -1, y[i] *= -1;
	repp(i, 1<<k, sz(x))
	{
		if (x[i] == inf) x[i] = -1;
		if (y[i] == inf) y[i] = -1;
	}
	x.erase(x.begin());
	y.erase(y.begin());
	answer(c, x, y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Output is partially correct
2 Partially correct 90 ms 9564 KB Output is partially correct
3 Partially correct 86 ms 9556 KB Output is partially correct
4 Partially correct 83 ms 10580 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Output is partially correct
2 Partially correct 90 ms 9564 KB Output is partially correct
3 Partially correct 86 ms 9556 KB Output is partially correct
4 Partially correct 83 ms 10580 KB Output is partially correct
5 Partially correct 93 ms 11224 KB Output is partially correct
6 Partially correct 96 ms 11220 KB Output is partially correct
7 Partially correct 115 ms 11528 KB Output is partially correct
8 Partially correct 86 ms 11068 KB Output is partially correct
9 Partially correct 86 ms 9552 KB Output is partially correct
10 Partially correct 114 ms 10896 KB Output is partially correct
11 Partially correct 92 ms 10724 KB Output is partially correct
12 Partially correct 87 ms 9796 KB Output is partially correct
13 Partially correct 82 ms 10308 KB Output is partially correct
14 Partially correct 86 ms 10312 KB Output is partially correct
15 Partially correct 82 ms 10308 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 42 ms 5800 KB Output is correct
18 Partially correct 79 ms 9724 KB Output is partially correct
19 Partially correct 81 ms 9908 KB Output is partially correct
20 Partially correct 92 ms 10812 KB Output is partially correct
21 Partially correct 93 ms 10576 KB Output is partially correct
22 Partially correct 88 ms 10584 KB Output is partially correct