Submission #1124001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124001		allin27x	Sorting (IOI15_sorting)	C++17	100 / 100	220 ms	12168 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]]);
	vector<int> bad(n+1,0); for (int i=0; i<n; i++) if (a[i] != s[i]) bad[s[i]] = 1;
	bad[n] = 1;
	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;
	int lb = 0;
	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]]]);

		int b = lb; while (!bad[b]) b = ++lb; if (lb == n) {p[ind] =0; q[ind] = 0; continue;};
		int i = poss[b]; int j = posa[b];
		p[ind] = i; q[ind] = j;
		bad[b] = 0;
		swap(s[i], s[j]); swap(poss[s[i]], poss[s[j]]);
		if (s[i] == a[i]) bad[s[i]] = 0;
	}
	while (!bad[lb]) lb++;
	if (lb == n) 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