Submission #258655

#	Time	Username	Problem	Language	Result	Execution time	Memory
258655		atoiz	Swap (BOI16_swap)	C++14	0 / 100	1 ms	1152 KiB

swap

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cassert>

using namespace std;

const int MAXN = 200007;
int N, A[MAXN * 2], last[MAXN];
struct Swap { int prv, x, y; bool used; };
vector<Swap> swaps;

void doSwap(int i, int j)
{
	if (i == j) return;
	swap(A[i], A[j]);
	for (int id = last[i]; ~id && (swaps[id].x == i || swaps[id].y == i); id = swaps[id].prv) {
		(swaps[id].x == i ? swaps[id].x : swaps[id].y) = j;
	}

	for (int id = last[j]; ~id && (swaps[id].x == j || swaps[id].y == j); id = swaps[id].prv) {
		(swaps[id].x == j ? swaps[id].x : swaps[id].y) = i;
	}
	swap(last[i], last[j]);
}

int getMin(int x)
{
	int ans = A[x];
	for (int id = last[x]; ~id && !swaps[id].used; id = swaps[id].prv) {
		ans = min(ans, min(A[swaps[id].x], A[swaps[id].y]));
	}
	return ans;
}

void retrieve(int x, int val)
{
	vector<pair<int, int>> todo;
	int opt = -1;
	for (int id = last[x]; ~id && (opt == -1 || (!swaps[id].used && (swaps[id].x == opt || swaps[id].y == opt))); id = swaps[id].prv) {
		if (A[swaps[id].x] == val) opt = swaps[id].x;
		if (A[swaps[id].y] == val) opt = swaps[id].y;

		assert(x == swaps[id].x || x == swaps[id].y);
		if (~opt) {
			if (x != opt) {
				todo.emplace_back(x, opt);
				x = opt;
			}
		} else {
			assert(~swaps[id].prv);
			int prv = swaps[id].prv;
			if (x != swaps[prv].x && x != swaps[prv].y) {
				int y = x ^ swaps[id].x ^ swaps[id].y;
				todo.emplace_back(x, y);
				x = y;
			}
		}
		
		swaps[id].used = true;
	}

	// assert(x == opt);

	// cout << "S" << endl;
	// cout << x << ' ' << opt << ' ' << A[opt] << endl;
	for (; !todo.empty(); todo.pop_back()) {
		// cout << todo.back().first << " - " << todo.back().second << endl;
		doSwap(todo.back().first, todo.back().second);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	for (int i = N + 1; i <= 2 * N + 1; ++i) A[i] = MAXN;
	memset(last, -1, sizeof last);

	for (int i = 1; i <= N; ++i) {
		int cur = getMin(i);
		int minVal = min(cur, min(A[i << 1], A[i << 1 | 1]));
		// cout << "min " << i << ": " << minVal << endl;
		if (cur == minVal) {
			retrieve(i, cur);
		} else if (A[i << 1] == minVal) {
			doSwap(i, i << 1);
		} else {
			doSwap(i, i << 1 | 1);
			swaps.push_back({last[i << 1 | 1], i << 1, i << 1 | 1, false});
			last[i << 1] = last[i << 1 | 1] = (int) swaps.size() - 1;
		}
		// cout << i << " = ";
		// for (int i = 1; i <= N; ++i) cout << A[i] << ' '; cout << endl;
		assert(A[i] == minVal);
	}

	for (int i = 1; i <= N; ++i) cout << A[i] << ' ';
	cout << endl;
}

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