제출 #437609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437609		Sohsoh84	즐거운 행로 (APIO20_fun)	C++14	0 / 100	1 ms	332 KiB

fun

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

struct Node {
	int v = 0, b = 0;
	Node *l = nullptr, *r = nullptr;
	Node(int v) : v(v) { Update(); }
	Node(int n, int v) : v(v) {
		if ((v << 1) <= n) l = new Node(n, v << 1);
		if ((v << 1 | 1) <= n) r = new Node(n, v << 1 | 1);
		Update();
	}

	void Update() {
		b = v;
		if (l) b = max(b, l -> b);
		if (r) b = max(b, r -> b);
	}

	int Remove() {
		if (!l && !r) return true;
		if (l && b == l -> v) l = nullptr;
		if (r && b == r -> v) r = nullptr;
		if (l && b == l -> b) l -> Remove();
		if (r && b == r -> b) r -> Remove();
		Update();
		return false;
	}
};

vector<int> ans;
int n;

void Majik(Node* v) {
	if (!v) return;
	Node* l = v -> l, *r = v -> r;
	if (!l && !r) {
		ans.push_back(v -> v);		
		return;
	}

	bool L = true;
	while (true) {	
		if (L) {
			ans.push_back(l -> b);
			if (l -> Remove()) {
				if (r) {
					ans.push_back(r -> b);
					r -> Remove();
				}

				break;
			}


		} else {
			if (!r) {
				Majik(l);
				break;
			}

			ans.push_back(r -> b);
			if (r -> Remove()) {
				Majik(l);
				break;
			}
		}

		L = !L;
	}

	ans.push_back(v -> v);
}

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

	Node* r = new Node(n, 1);
	Majik(r);
	
	
	for (int& e : ans) e--;
	return ans;
}

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