Submission #1240095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240095		kaiboy	Swap (BOI16_swap)	C++20	100 / 100	54 ms	13640 KiB

swap

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

using namespace std;

const int   N = 200000;
const int INF = 0x3f3f3f3f;

int aa[N + 1];
vector<int> ej[N + 1];
bool usedi[N + 1], useda[N + 1];

int dfs(int i) {
	if (i < 0) {
		int a = -i;
		return useda[a] ? INF : a;
	}
	if (usedi[i])
		return INF;
	int a = INF;
	for (int j : ej[i])
		a = min(a, dfs(j));
	return a;
}

bool dfs(int i, int a_) {
	if (i < 0) {
		int a = -i;
		if (useda[a])
			return false;
		return useda[a] = a == a_;
	}
	if (usedi[i])
		return false;
	for (int j : ej[i])
		if (dfs(j, a_))
			return usedi[i] = true;
	return false;
}

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

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