Submission #1286843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286843		Jawad_Akbar_JJ	Sorting (IOI15_sorting)	C++20	100 / 100	120 ms	14060 KiB

sorting

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair<int, int>> vec;
int ind[1<<18], s2[1<<18], seen[1<<18];

int getSwaps(int n, int s[], int m, int x[], int y[]){
	vec.clear();
	for (int i=0;i<n;i++)
		s2[i] = s[i], seen[i] = 0;

	for (int i=0;i<m;i++)
		swap(s2[x[i]], s2[y[i]]);

	for (int i=0;i<n;i++){
		if (seen[i])
			continue;
		
		while (!seen[i]){
			vec.push_back({s2[s2[i]], s2[i]});
			seen[i] = 1;
			i = s2[i];
		}
		vec.pop_back();
	}
	return vec.size();
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]){
	int l = -1, r = m;
	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (getSwaps(n, s, mid, x, y) <= mid)
			r = mid;
		else
			l = mid;
	}

	m = r;
	getSwaps(n, s, m, x, y);

	for (int i=0;i<n;i++)
		ind[s[i]] = i;

	reverse(begin(vec), end(vec));
	for (int i=0;i<m;i++){
		swap(s[x[i]], s[y[i]]);
		swap(ind[s[x[i]]], ind[s[y[i]]]);

		if (vec.size() > 0){
			auto [a, b] = vec.back();
			vec.pop_back();
			p[i] = ind[a], q[i] = ind[b];
			swap(s[p[i]], s[q[i]]);
			swap(ind[s[p[i]]], ind[s[q[i]]]);
		}
		else
			p[i] = q[i] = 0;
	}
	return m;
}

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