Submission #1226100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226100		Jer	Fun Tour (APIO20_fun)	C++20	0 / 100	0 ms	324 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;
const int MAXN = 100005;
bool used[MAXN];
int m[MAXN];
int n;

int dfs(int i, int d){
	if (2 * i + 1 >= n) {m[i] = d; return d;}
	m[i] = dfs(2 * i + 1, d + 1);
	if (2 * i + 2 < n) dfs(2 * i + 2, d + 1);
	return m[i];
}

int find_deepest(int i){
	if (2 * i + 1 >= n) {used[i] = true, m[i]--; return i;}

	int res = m[i];

	if (!used[2 * i + 1] and !used[2 * i + 2]){
		if (m[2 * i + 1] >= m[2 * i + 2])
			res = find_deepest(2 * i + 1);
		else
			res = find_deepest(2 * i + 2);
		m[i] = max(m[2 * i + 1], m[2 * i + 2]);
		return res;
	}

	if (used[2 * i + 1] and !used[2 * i + 2]){
		res = find_deepest(2 * i + 2);
		m[i] = max(m[2 * i + 1], m[2 * i + 2]);
		return res;
	}

	if (!used[2 * i + 1] and used[2 * i + 2])
	{
		res = find_deepest(2 * i + 1);
		m[i] = max(m[2 * i + 1], m[2 * i + 2]);
		return res;
	}

	used[i] = true, m[i]--;
	return i;
}

std::vector<int> createFunTour(int N, int Q) {
	if (n == 2)	return {0, 1};

	n = N;
	vector<int> res;

	dfs(0, 0);

	int curr = 0, r, l;
	for (int i = 0; i <= n; i += 2){
		r = -1;
		if (used[2 * curr + 2])
			r = curr, curr = 2 * curr + 1;
		if (r == -1) r = find_deepest(2 * curr + 2);

		l = (used[2 * curr + 1]) ? curr : find_deepest(curr);

		if (l == curr)
			res.push_back(r);
		else
			res.push_back(l), res.push_back(r);
	}
	
	res.push_back(curr);

	return res;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34