Submission #1124000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124000		allin27x	Sorting (IOI15_sorting)	C++17	100 / 100	878 ms	22080 KiB

sorting

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


int solveforM(int n, int st[], int m, int x[], int y[], int p[], int q[]) {
	vector<int> a(n); iota(a.begin(), a.end(), 0);
	vector<int> s(n); for (int i=0; i<n; i++) s[i] = st[i];
	for (int i=m-1; i>=0; i--) swap(a[x[i]], a[y[i]]);
	unordered_set<int> bad; for (int i=0; i<n; i++) if (a[i] != s[i]) bad.insert(s[i]);
	vector<int> posa(n); for (int i=0; i<n; i++) posa[a[i]] = i;
	vector<int> poss(n); for (int i=0; i<n; i++) poss[s[i]] = i;
	for (int ind=0; ind<m; ind++) {
		p[ind] = 0; q[ind] = 0;
		swap(a[x[ind]], a[y[ind]]); swap(s[x[ind]], s[y[ind]]);
		swap(posa[a[x[ind]]], posa[a[y[ind]]]); swap(poss[s[x[ind]]], poss[s[y[ind]]]);
		if (bad.empty()) {
			p[ind] = 0; q[ind] = 0; continue;
		}
		int b = *bad.begin();
		int i = poss[b]; int j = posa[b];
		p[ind] = i; q[ind] = j;
		bad.erase(b);
		swap(s[i], s[j]); swap(poss[s[i]], poss[s[j]]);
		if (s[i] == a[i]) bad.erase(s[i]);
	}
	if (bad.empty()) return m;
	return 1e9;

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

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