Submission #1247109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247109		countless	Sorting (IOI15_sorting)	C++20	0 / 100	1096 ms	576 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
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;
	bool ok = false;
	while (!ok) {
		for (int i = N-1; i >= 0; i--) {
			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())) {
				ok = true;
				break;
			}
			// for (auto &x : A) cerr << x << " ";
			// cerr << endl;
		}
	}

	return r;
}

// 3 0 4 2 1
// 

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