oj.uz

Submission #1059834

# Submission time Handle Problem Language Result Execution time Memory
1059834 2024-08-15T08:34:37 Z jerzyk Mechanical Doll (IOI18_doll) C++17
100 / 100
 89 ms 23800 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int L, lft;
int tab[N];
int l[N], r[N], num[N], cnt = 0;
vector<pair<int, int>> pos;
vector<int> AX, AY;

void Rem(int v, int siz)
{
	if(lft == 0 || siz == 1) return;
	if(siz / 2 <= lft)
	{
		l[v] = -1;
		lft -= siz / 2;
	}
	if(l[v] != -1)
		Rem(v * 2, siz / 2);
	else
		Rem(v * 2 + 1, siz / 2);
}

void FindPos(int v, int num, int wys)
{
	if(v >= L)
	{
		pos.pb(make_pair(num, v));
		return;
	}
	if(l[v] != -1)
		FindPos(v * 2, num, wys + 1);
	FindPos(v * 2 + 1, num + (1<<wys), wys + 1);
}

void Fin(int v)
{
	--cnt; num[v] = cnt;
	if(l[v] == 0 && v * 2 < L)
	{
		Fin(v * 2);
		l[v] = num[v * 2];
	}
	if(r[v] == 0 && v * 2 < L)
	{
		Fin(v * 2 + 1);
		r[v] = num[v * 2 + 1];
	}
}

void DoOut(int v)
{
	//cerr << v << " " << l[v] << " " << r[v] << "\n";
	AX.pb(l[v]); AY.pb(r[v]);
	if(l[v] < -1)
		DoOut(v * 2);
	if(r[v] < -1)
		DoOut(v * 2 + 1);
}

void DoB(int n)
{
	L = 2;
	while(L < n)
		L *= 2;
	lft = L - n;
	Rem(1, L);
	FindPos(1, 0, 0);
	sort(pos.begin(), pos.end());
	for(int i = 1; i <= n; ++i)
	{
		int o = pos[i - 1].nd / 2;
		if(pos[i - 1].nd % 2 == 0)
			l[o] = tab[i];
		else
			r[o] = tab[i];
	}
	Fin(1);
	DoOut(1);
}

void create_circuit(int M, vector<int> A)
{
	int n = A.size();
	vector<int> C, X, Y;
	for(int i = 1; i < n; ++i)
		tab[i] = A[i];
	C.pb(A[0]);
	for(int i = 1; i <= M; ++i)
		C.pb(-1);
	DoB(n);
	//cerr << "exit " << AX.size() << " " << AY.size() << "\n";
	answer(C, AX, AY);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 40 ms 11236 KB Output is correct
3 Correct 23 ms 11700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 42 ms 16008 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 40 ms 11236 KB Output is correct
3 Correct 23 ms 11700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 42 ms 16008 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 36 ms 17220 KB Output is correct
9 Correct 44 ms 17696 KB Output is correct
10 Correct 84 ms 22224 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 40 ms 11236 KB Output is correct
3 Correct 23 ms 11700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 6 ms 5844 KB Output is correct
6 Correct 42 ms 16008 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 36 ms 17220 KB Output is correct
9 Correct 44 ms 17696 KB Output is correct
10 Correct 84 ms 22224 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 68 ms 21688 KB Output is correct
15 Correct 42 ms 15040 KB Output is correct
16 Correct 64 ms 21684 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 59 ms 23800 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 58 ms 16340 KB Output is correct
3 Correct 32 ms 16064 KB Output is correct
4 Correct 89 ms 20640 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 58 ms 16340 KB Output is correct
3 Correct 32 ms 16064 KB Output is correct
4 Correct 89 ms 20640 KB Output is correct
5 Correct 60 ms 21656 KB Output is correct
6 Correct 59 ms 21596 KB Output is correct
7 Correct 57 ms 21572 KB Output is correct
8 Correct 59 ms 21796 KB Output is correct
9 Correct 32 ms 14280 KB Output is correct
10 Correct 57 ms 21480 KB Output is correct
11 Correct 56 ms 20984 KB Output is correct
12 Correct 32 ms 16480 KB Output is correct
13 Correct 37 ms 16836 KB Output is correct
14 Correct 38 ms 16756 KB Output is correct
15 Correct 35 ms 16728 KB Output is correct
16 Correct 3 ms 4840 KB Output is correct
17 Correct 34 ms 16576 KB Output is correct
18 Correct 33 ms 16440 KB Output is correct
19 Correct 32 ms 16320 KB Output is correct
20 Correct 59 ms 23220 KB Output is correct
21 Correct 58 ms 21172 KB Output is correct
22 Correct 74 ms 21052 KB Output is correct