Submission #147285

#	Time	Username	Problem	Language	Result	Execution time	Memory
147285		cerberus	Swap (BOI16_swap)	C++17	0 / 100	2 ms	376 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);
void del(node *cur, int x);

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		a[i] = new node(NULL, NULL, x);
	}
	for (int i = n + 1; i <= 2 * n + 1; ++i) {
		a[i] = new node(NULL, NULL);
	}
	for (int i = 1; i <= n; ++i) {
		int x = get_min(a[i]);
		x = min(x, min(get_min(a[2 * i]), get_min(a[2 * i + 1])));
		cout << 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);
	}
}

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;
	}
}

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

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