oj.uz

Submission #1068867

# Submission time Handle Problem Language Result Execution time Memory
1068867 2024-08-21T12:40:45 Z Joshua_Andersson Mechanical Doll (IOI18_doll) C++14
47 / 100
 138 ms 11324 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

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

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(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, sz(x)) x[i] *= -1, y[i] *= -1;
	rep(i, 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 0 ms 348 KB Output is partially correct
2 Correct 53 ms 5992 KB Output is correct
3 Partially correct 103 ms 9572 KB Output is partially correct
4 Partially correct 107 ms 10580 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 53 ms 5992 KB Output is correct
3 Partially correct 103 ms 9572 KB Output is partially correct
4 Partially correct 107 ms 10580 KB Output is partially correct
5 Partially correct 103 ms 11224 KB Output is partially correct
6 Partially correct 134 ms 11324 KB Output is partially correct
7 Partially correct 108 ms 11324 KB Output is partially correct
8 Partially correct 114 ms 11068 KB Output is partially correct
9 Partially correct 97 ms 9568 KB Output is partially correct
10 Partially correct 113 ms 10900 KB Output is partially correct
11 Partially correct 101 ms 10640 KB Output is partially correct
12 Partially correct 138 ms 9812 KB Output is partially correct
13 Correct 50 ms 6292 KB Output is correct
14 Partially correct 95 ms 10400 KB Output is partially correct
15 Partially correct 93 ms 10432 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Correct 45 ms 5972 KB Output is correct
18 Correct 54 ms 5800 KB Output is correct
19 Partially correct 101 ms 9800 KB Output is partially correct
20 Partially correct 109 ms 10808 KB Output is partially correct
21 Partially correct 108 ms 10656 KB Output is partially correct
22 Partially correct 113 ms 10784 KB Output is partially correct