oj.uz

Submission #139037

# Submission time Handle Problem Language Result Execution time Memory
139037 2019-07-31T08:25:46 Z Mahdi_Jfri Mechanical Doll (IOI18_doll) C++14
84 / 100
 207 ms 17408 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);

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 58 ms 11888 KB Output is correct
3 Correct 51 ms 11768 KB Output is correct
4 Correct 7 ms 8012 KB Output is correct
5 Correct 19 ms 9380 KB Output is correct
6 Correct 85 ms 13352 KB Output is correct
7 Incorrect 6 ms 8100 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 58 ms 11888 KB Output is correct
3 Correct 51 ms 11768 KB Output is correct
4 Correct 7 ms 8012 KB Output is correct
5 Correct 19 ms 9380 KB Output is correct
6 Correct 85 ms 13352 KB Output is correct
7 Incorrect 6 ms 8100 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 58 ms 11888 KB Output is correct
3 Correct 51 ms 11768 KB Output is correct
4 Correct 7 ms 8012 KB Output is correct
5 Correct 19 ms 9380 KB Output is correct
6 Correct 85 ms 13352 KB Output is correct
7 Incorrect 6 ms 8100 KB Output isn't correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8012 KB Output is correct
2 Correct 123 ms 12788 KB Output is correct
3 Correct 101 ms 12772 KB Output is correct
4 Correct 142 ms 15292 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8012 KB Output is correct
2 Correct 123 ms 12788 KB Output is correct
3 Correct 101 ms 12772 KB Output is correct
4 Correct 142 ms 15292 KB Output is correct
5 Correct 207 ms 17408 KB Output is correct
6 Correct 153 ms 15988 KB Output is correct
7 Correct 128 ms 16056 KB Output is correct
8 Correct 135 ms 16632 KB Output is correct
9 Correct 165 ms 12776 KB Output is correct
10 Correct 149 ms 15608 KB Output is correct
11 Correct 145 ms 15276 KB Output is correct
12 Correct 89 ms 12784 KB Output is correct
13 Correct 82 ms 14136 KB Output is correct
14 Correct 102 ms 13304 KB Output is correct
15 Correct 83 ms 13416 KB Output is correct
16 Correct 9 ms 8268 KB Output is correct
17 Correct 96 ms 14112 KB Output is correct
18 Correct 98 ms 12772 KB Output is correct
19 Correct 87 ms 12784 KB Output is correct
20 Correct 144 ms 16480 KB Output is correct
21 Correct 146 ms 15288 KB Output is correct
22 Correct 120 ms 15284 KB Output is correct