oj.uz

Submission #258663

# Submission time Handle Problem Language Result Execution time Memory
258663 2020-08-06T10:50:12 Z atoiz Swap (BOI16_swap) C++14
0 / 100
 1 ms 1152 KB 
#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)
{
	// cout << i << " <-> " << j << endl; 
	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) {
		// 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;
	}

	for (int id = last[j]; ~id && (swaps[id].x == j || swaps[id].y == j); id = swaps[id].prv) {
		// cout << "(" << swaps[id].x << ' ' << swaps[id].y << ")"; cout << " ---> ";
		(swaps[id].x == j ? swaps[id].x : swaps[id].y) = i;
		// cout << "(" << swaps[id].x << ' ' << swaps[id].y << ")"; cout << endl;
	}
	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) {
				assert(!swaps[id].used);
				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;
				assert(!swaps[id].used);
				todo.emplace_back(x, y);
				x = y;
			}
		}

		swaps[id].used = true;
	}

	for (; !todo.empty(); todo.pop_back()) {
		swap(A[todo.back().first], A[todo.back().second]);
		// 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]));
		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;
		}
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Halted 0 ms 0 KB -