Submission #147294

#	Time	Username	Problem	Language	Result	Execution time	Memory
147294		cerberus	Swap (BOI16_swap)	C++17	100 / 100	230 ms	23928 KiB

swap

/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 4e5 + 10, inf = 1e9 + 42;

struct node {
	int val;
	node *l, *r;
	node(node *_l, node *_r, int _val = inf) {
		l = _l;
		r = _r;
		val = _val;
	}
};

node* a[N];

int get_min(node* cur);
bool del(node *cur, int x);

int main() {
	int n; cin >> n;
	vector<int> p(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		a[i] = new node(NULL, NULL, x);
		p[i] = x;
	}
	for (int i = n + 1; i <= 2 * n + 1; ++i) {
		a[i] = new node(NULL, NULL);
	}
	vector<int> q(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int x = get_min(a[i]);
		x = min(x, get_min(a[2 * i]));
		x = min(x, get_min(a[2 * i + 1]));
		// cout << x << ' ';
		q[i] = x;
		if (get_min(a[2 * i]) == x) {
			swap(a[2 * i], a[i]);
		} else if (get_min(a[2 * i + 1]) == x) {
			node *temp = new node(a[i], a[2 * i]);
			a[i] = a[2 * i + 1];
			a[2 * i] = a[2 * i + 1] = temp;
		}
		del(a[i], x);
	}
	vector<int> ans = q;
	for (int i = n; i > 1; --i) {
		if (q[i] != p[i]) {
			swap(q[i], q[i / 2]);
		}
	}
	assert(p == q);
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << ' ';
	}
	cout << endl;
}

int get_min(node* cur) {
	if (cur == NULL) {
		return inf;
	} else {
		int ans = cur->val;
		ans = min(ans, get_min(cur->l));
		ans = min(ans, get_min(cur->r));
		return ans;
	}
}

bool del(node *cur, int x) {
	if (cur == NULL) {
		return false;
	} else if (cur->val == x) {
		cur->val = inf;
		return true;
	} else {
		if (del(cur->l, x)) {
			cur->l = NULL;
		} else if (del(cur->r, x)) {
			cur->r = NULL;
		} else {
			return false;
		}
		return true;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32