oj.uz

Submission #1068532

# Submission time Handle Problem Language Result Execution time Memory
1068532 2024-08-21T10:29:47 Z Joshua_Andersson Mechanical Doll (IOI18_doll) C++14
47 / 100
 103 ms 11320 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);
	vi c(m + 1, -1);
	c[0] = a[0];
	n--;
	a.erase(a.begin());
	while ((1<<(k+1))<=n)
	{
		k++;
	}

	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 344 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 344 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 41 ms 6008 KB Output is correct
3 Partially correct 88 ms 9660 KB Output is partially correct
4 Partially correct 99 ms 10576 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 41 ms 6008 KB Output is correct
3 Partially correct 88 ms 9660 KB Output is partially correct
4 Partially correct 99 ms 10576 KB Output is partially correct
5 Partially correct 90 ms 11224 KB Output is partially correct
6 Partially correct 100 ms 11316 KB Output is partially correct
7 Partially correct 95 ms 11320 KB Output is partially correct
8 Partially correct 90 ms 11172 KB Output is partially correct
9 Partially correct 89 ms 9552 KB Output is partially correct
10 Partially correct 89 ms 10916 KB Output is partially correct
11 Partially correct 103 ms 10780 KB Output is partially correct
12 Partially correct 83 ms 9816 KB Output is partially correct
13 Correct 44 ms 6216 KB Output is correct
14 Partially correct 87 ms 10400 KB Output is partially correct
15 Partially correct 81 ms 10424 KB Output is partially correct
16 Partially correct 3 ms 604 KB Output is partially correct
17 Correct 39 ms 5972 KB Output is correct
18 Correct 43 ms 5968 KB Output is correct
19 Partially correct 93 ms 9736 KB Output is partially correct
20 Partially correct 87 ms 10884 KB Output is partially correct
21 Partially correct 90 ms 10660 KB Output is partially correct
22 Partially correct 88 ms 10660 KB Output is partially correct