Submission #1240060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240060		kaiboy	Swap (BOI16_swap)	C++20	0 / 100	2 ms	4932 KiB

swap

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 200000;

vector<int> aa[N + 1];
bool used[N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		aa[i].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		int l = i << 1, r = l ^ 1, a_ = n + 1;
		for (int a : aa[i])
			if (!used[a])
				a_ = min(a_, a);
		if (l > n) {
			cout << a_ << ' ', used[a_] = true;
			continue;
		}
		int al = aa[l][0];
		if (r > n) {
			if (a_ < al) {
				cout << a_ << ' ', used[a_] = true;
				continue;
			}
			cout << al << ' ', used[al] = true;
			aa[l].clear();
			for (int a : aa[i])
				if (!used[a])
					aa[l].push_back(a);
			continue;
		}
		int ar = aa[r][0];
		if (a_ < al && a_ < ar) {
			cout << a_ << ' ', used[a_] = true;
			continue;
		}
		if (al < ar) {
			cout << al << ' ', used[al] = true;
			aa[l].clear();
			for (int a : aa[i])
				if (!used[a])
					aa[l].push_back(a);
			continue;
		}
		cout << ar << ' ', used[ar] = true;
		for (int a : aa[i])
			if (!used[a])
				aa[l].push_back(a);
		aa[r] = aa[l];
	}
	cout << '\n';
	return 0;
}

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