Submission #1247149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247149		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 (!vis[at]) {
				vis[at] = true;
				at = S[at];
			}

			cyc++;
		}

		return N - cyc <= x;
	};

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

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

			vector<int> cyc;
			int at = i;
			while (!vis[at]) {
				vis[at] = true;
				cyc.push_back(at);
				at = A[at];
			}

			for(int j = 1; j < cyc.size(); j++) {
				P[id] = cyc[0], Q[id] = cyc[j];
				id++;
				swap(A[cyc[0]], A[cyc[j]]);
			}
		}
	};

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

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

	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