제출 #258683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258683		atoiz	Swap (BOI16_swap)	C++14	0 / 100	2 ms	2176 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 reassign(int i, int j)
{
	for (int id = last[i]; ~id && (swaps[id].x == i || swaps[id].y == i); id = swaps[id].prv) {
		// cout << "(" << swaps[id].x << ' ' << swaps[id].y << ")"; cout << " ---> ";
		(swaps[id].x == i ? swaps[id].x : swaps[id].y) = j;
		// cout << "(" << swaps[id].x << ' ' << swaps[id].y << ")"; cout << endl;
	}
	last[j] = last[i];
}

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;
	for (int id = last[x]; ~id && !swaps[id].used; id = swaps[id].prv) {
		swaps[id].used = true;
		assert(x == swaps[id].x || x == swaps[id].y);
		int y = x ^ swaps[id].x ^ swaps[id].y;

		int prv = swaps[id].prv;
		if (A[y] == val || (~prv && x != swaps[prv].x && x != swaps[prv].y)) {
			if (A[x] == val) break;
			todo.emplace_back(x, y);
			x = y;
		}
	}

	for (; !todo.empty(); todo.pop_back()) swap(A[todo.back().first], A[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]));
		if (cur == minVal) {
			retrieve(i, cur);
		} else if (A[i << 1] == minVal) {
			swap(A[i], A[i << 1]);
			reassign(i, i << 1);
		} else {
			swap(A[i], A[i << 1 | 1]);
			reassign(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;
		}
		for (int id = last[i]; ~id && (swaps[id].x == i || swaps[id].y == i); id = swaps[id].prv) {
			swaps[id].used = true;
		}

		// 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