Submission #1247165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247165		SpyrosAliv	Sorting (IOI15_sorting)	C++20	16 / 100	5 ms	328 KiB

sorting

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

void sw(int i, int j, int pos[], int p[], int q[], int arr[], int tot) {
	if (tot != -1) {
		p[tot] = pos[i];
		q[tot] = pos[j];
	}
	swap(pos[i], pos[j]);
	swap(arr[pos[i]], arr[pos[j]]);
}

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++) {
		sw(arr[should[i]], arr[pos[i]], pos, p, q, arr, i);
		if (i < n-1) {
			sw(arr[x[i+1]], arr[y[i+1]], pos, p, q, arr, -1);
		}
	}
	for (int i = n; i < m; i++) {
		sw(arr[x[i]], arr[y[i]], pos, p, q, arr, -1);
		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: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26