Submission #1247154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247154		SpyrosAliv	Sorting (IOI15_sorting)	C++20	0 / 100	4 ms	328 KiB

sorting

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

int findSwapPairs(int N, int arr[], int m, int x[], int y[], int p[], int q[]) {
	int n = N;
	swap(arr[x[0]], arr[y[0]]);
	vector<int> endsUp(n, -1);
	for (int i = 0; i < n; i++) {
		int lastPlace = i;
		for (int j = m-1; j >= i + 1; j--) {
			if (x[j] == lastPlace || y[j] == lastPlace) {
				lastPlace ^= (x[j] ^ y[j]);
			}
		}
		endsUp[i] = lastPlace;
	}
	int pos[n], should[n];
	for (int i = 0; i < n; i++) {
		pos[arr[i]] = i;
		should[i] = endsUp[i];
	}
	for (int i = 0; i < n; i++) {
		if (pos[i] == should[i]) {
			p[i] = q[i] = 0;
		}
		else {
			p[i] = pos[i];
			q[i] = should[i];
			swap(arr[pos[i]], arr[should[i]]);
			swap(pos[i], pos[arr[pos[i]]]);
		}
		if (i < n-1) {
			swap(arr[x[i + 1]], arr[y[i + 1]]);
			swap(pos[x[i + 1]], pos[y[i + 1]]);
		}
	}
	for (int i = n; i < m; i++) {
		swap(arr[x[i]], arr[y[i]]);
		p[i] = q[i] = 0;
	}
	for (int i = 0; i < n; i++) cout << arr[i] << " ";
	cout << '\n';
	return m;
}

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