oj.uz

Submission #139040

# Submission time Handle Problem Language Result Execution time Memory
139040 2019-07-31T08:27:50 Z Mahdi_Jfri Mechanical Doll (IOI18_doll) C++14
100 / 100
 167 ms 17432 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 1e6 + 20;
const int maxb = 20;

int id , pt;
int x[maxn] , y[maxn];

vector<int> a , bits;

int build(int n)
{
	if(n == 0)
		return -1;

	int root = id++;
	x[root] = build(n - 1);
	y[root] = build(n - 1);

	return root;
}

int solve(int k , int n)
{
	if(n == (1 << k))
		return build(k);

	int root = id++;
	if(n <= (1 << (k - 1)))
	{
		x[root] = 0;
		y[root] = solve(k - 1 , n);
	}
	else
	{
		x[root] = build(k - 1);
		n -= (1 << (k - 1));
		y[root] = solve(k - 1 , n);
	}

	return root;
}

bool is[maxn];

void dfs(int v)
{
	while(pt < (int)a.size())
	{
		if(!is[v])
		{
			is[v] ^= 1;
			if(x[v] == -1)
			{
				x[v] = a[pt++] + maxn * 10 , v = 0;
			}
			else
			{
				v = x[v];
			}
		}
		else
		{
			is[v] ^= 1;
			if(y[v] == -1)
			{
				y[v] = a[pt++] + maxn * 10 , v = 0;
			}
			else
			{
				v = y[v];
			}
		}
	}
}

void create_circuit(int m, vector<int> A)
{
	memset(x , -1 , sizeof x);
	memset(y , -1 , sizeof y);

	if(A.size() == 1)
	{
		vector<int> shit , x;
		for(int i = 0; i <= m; i++)
			shit.pb(0);
		shit[0] = A[0];
		answer(shit , x , x);
		return;
	}

	a = A;
	a.pb(0);
	int n = a.size();

	for(int j = 0; j < 20; j++)
		if(bit(n , j))
			bits.pb(j);

	solve(bits.back() + 1 , n);

	dfs(0);

	for(int i = 0; i < id; i++)
	{
		int v = i;
		if(x[v] >= maxn * 10)
			x[v] = x[v] - maxn * 10;
		else
			x[v] = -x[v] - 1;

		if(y[v] >= maxn * 10)
			y[v] = y[v] - maxn * 10;
		else
			y[v] = -y[v] - 1;
	}

	vector<int> res;
	for(int i = 0; i <= m; i++)
		res.pb(-1);

	vector<int> X , Y;
	for(int i = 0; i < id; i++)
		X.pb(x[i]) , Y.pb(y[i]);
	answer(res , X , Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 59 ms 11956 KB Output is correct
3 Correct 53 ms 11764 KB Output is correct
4 Correct 5 ms 8048 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 79 ms 13328 KB Output is correct
7 Correct 5 ms 8040 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 59 ms 11956 KB Output is correct
3 Correct 53 ms 11764 KB Output is correct
4 Correct 5 ms 8048 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 79 ms 13328 KB Output is correct
7 Correct 5 ms 8040 KB Output is correct
8 Correct 89 ms 14256 KB Output is correct
9 Correct 111 ms 14532 KB Output is correct
10 Correct 167 ms 17280 KB Output is correct
11 Correct 5 ms 8012 KB Output is correct
12 Correct 7 ms 8012 KB Output is correct
13 Correct 6 ms 8064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 59 ms 11956 KB Output is correct
3 Correct 53 ms 11764 KB Output is correct
4 Correct 5 ms 8048 KB Output is correct
5 Correct 16 ms 9412 KB Output is correct
6 Correct 79 ms 13328 KB Output is correct
7 Correct 5 ms 8040 KB Output is correct
8 Correct 89 ms 14256 KB Output is correct
9 Correct 111 ms 14532 KB Output is correct
10 Correct 167 ms 17280 KB Output is correct
11 Correct 5 ms 8012 KB Output is correct
12 Correct 7 ms 8012 KB Output is correct
13 Correct 6 ms 8064 KB Output is correct
14 Correct 134 ms 16904 KB Output is correct
15 Correct 82 ms 14660 KB Output is correct
16 Correct 125 ms 17432 KB Output is correct
17 Correct 8 ms 8012 KB Output is correct
18 Correct 6 ms 8012 KB Output is correct
19 Correct 6 ms 8028 KB Output is correct
20 Correct 160 ms 16988 KB Output is correct
21 Correct 5 ms 8012 KB Output is correct
22 Correct 7 ms 8012 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 84 ms 12956 KB Output is correct
3 Correct 88 ms 12800 KB Output is correct
4 Correct 130 ms 15288 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 84 ms 12956 KB Output is correct
3 Correct 88 ms 12800 KB Output is correct
4 Correct 130 ms 15288 KB Output is correct
5 Correct 137 ms 17332 KB Output is correct
6 Correct 136 ms 15944 KB Output is correct
7 Correct 135 ms 15984 KB Output is correct
8 Correct 141 ms 16732 KB Output is correct
9 Correct 84 ms 12796 KB Output is correct
10 Correct 121 ms 15620 KB Output is correct
11 Correct 162 ms 15292 KB Output is correct
12 Correct 99 ms 12780 KB Output is correct
13 Correct 87 ms 14116 KB Output is correct
14 Correct 106 ms 13300 KB Output is correct
15 Correct 86 ms 13348 KB Output is correct
16 Correct 10 ms 8268 KB Output is correct
17 Correct 89 ms 14128 KB Output is correct
18 Correct 101 ms 12780 KB Output is correct
19 Correct 85 ms 12772 KB Output is correct
20 Correct 129 ms 16548 KB Output is correct
21 Correct 148 ms 15288 KB Output is correct
22 Correct 122 ms 15292 KB Output is correct