Submission #1247114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247114		countless	Sorting (IOI15_sorting)	C++20	36 / 100	2 ms	584 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"

// build graph and just solve in 3N.
// where does each index go after 3N?
// how do our swaps change the graph
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[]) {
	// insertion sort.
	vector<int> A(N), at(N);
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		at[A[i]] = i;
	}

	// for (auto &x : A) cerr << x << " ";
	// cerr << endl;
	
	int r = 0;
	if (is_sorted(A.begin(), A.end())) return r;
	bool ok = false;
	while (!ok) {
		if (is_sorted(A.begin(), A.end())) return r;
		vector<int> o(N);
		iota(o.begin(), o.end(), 0);
		shuffle(o.begin(), o.end(), rng);

		for (int j = N-1; j >= 0; j--) {
			int i = o[j];
			if (A[i] == i) continue;

			// cerr << "ele:" sp A[i] sp "at" sp i << endl;

			// perform X[i], Y[i] swap
			swap(at[A[X[i]]], at[A[Y[i]]]);
			swap(A[X[i]], A[Y[i]]);

			// cerr << "ermek:" sp A[X[i]] sp "and" sp A[Y[i]] << endl;

			// we don't really need to save swaps for st1-3 for now
			int at1 = at[i], at2 = i;
			int el1 = A[at[i]], el2 = A[i];

			P[r] = at1, Q[r] = at2;
			r++;

			swap(at[el1], at[el2]);
			swap(A[at1], A[at2]);

			// cerr << "aizhan:" sp el1 sp "and" sp el2 << endl;

			if (is_sorted(A.begin(), A.end())) return r;
			// for (auto &x : A) cerr << x << " ";
			// cerr << endl;
		}
	}

	return r;
}

// 3 0 4 2 1
// 

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