Submission #1247155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247155		countless	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	328 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	if (is_sorted(S, S+N)) return 0;

	int id = 0;

	auto check = [&](int x) -> bool {
		vector<int> targ(N), inv(N);
		iota(targ.begin(), targ.end(), 0);
		for (int i = 0; i < x; i++) {
			swap(targ[X[i]], targ[Y[i]]);
		}

		vector<bool> vis(N);
		int cyc = 0;
		for (int i = 0; i < N; i++) {
			if (vis[i]) continue;

			int at = i;
			while (S[at] != targ[at] and !vis[at]) {
				vis[at] = true;
				at = S[at];
			}

			cyc++;
		}

		return N - cyc <= x;
	};

	auto apply = [&](int x) -> void {
		vector<int> targ(N), inv(N);
		for (int i = 0; i < N; i++) targ[i] = S[i];
		for (int i = 0; i < x; i++) {
			swap(targ[X[i]], targ[Y[i]]);
		}

		for (int i = 0; i < N; i++) inv[S[i]] = i;

		vector<bool> vis(N, 0);
		int id = 0;
    	for (int i = 0; i < N; i++) {
			if (vis[i]) continue;

			int at = i;
			vis[at] = true;
			while (!vis[targ[at]]) {
				vis[targ[at]] = true;
				swap(S[X[id]], S[Y[id]]);
				inv[S[X[id]]] = X[id];
				inv[S[Y[id]]] = Y[id];
				P[id] = inv[targ[at]];
				Q[id] = inv[targ[targ[at]]];
				swap(S[P[id]], S[Q[id]]);
				inv[S[P[id]]] = P[id];
				inv[S[Q[id]]] = Q[id];
				at = targ[at];
				id++;
			}
		}
	};

	int l = 0, r = N;
	while (r - l > 1) {
		int m = (l + r) / 2;

		if (check(m)) {
			r = m;
		} else {
			l = m;
		}
	}

	cerr << r << endl;
	apply(r);
	return r;
}

// 3 0 4 2 1
// 

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26