Submission #1229164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229164		PlayVoltz	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	584 KiB

sorting

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
vector<int> ss, x, y;
vector<pii> ans;

bool check(int m){
	ans.clear();
	ans.resize(m, mp(0, 0));
	vector<int> f(n), id(n), s=ss, b(n), bid(n);
	for (int i=0; i<n; ++i)f[i]=i, id[s[i]]=i;
	for (int i=0; i<m; ++i)swap(f[x[i]], f[y[i]]);
	for (int i=0; i<n; ++i)b[f[i]]=i, bid[b[f[i]]]=i;
	int p=0;
	for (int i=0; i<m; ++i){
		swap(s[x[i]], s[y[i]]);
		//swap(b[x[i]], b[y[i]]);
		id[s[x[i]]]=x[i];
		id[s[y[i]]]=y[i];
		//bid[b[x[i]]]=x[i];
		//bid[b[y[i]]]=y[i];
		int v1 = s[x[i]];
		int v2 = s[y[i]];
		id [v1] = x[i];  id [v2] = y[i];
		b  [v1] = x[i];  b  [v2] = y[i];
		bid[x[i]] = v1;  bid[y[i]] = v2;
		while (p<n&&id[p]==bid[p])++p;
		if (p==n)break;
		pii temp = mp(id[p], bid[p]);
		swap(s[temp.fi], s[temp.se]);
		id[s[temp.fi]]=temp.fi;
		id[s[temp.se]]=temp.se;
		ans[i]=temp;
	}
	while (p<n&&id[p]==bid[p])++p;
	return p==n;
}

int findSwapPairs(int N, int S[], int m, int X[], int Y[], int p[], int q[]){
	n=N;
	ss.clear();
	x.clear();
	y.clear();
	ss.resize(n);
	x.resize(m);
	y.resize(m);
	for (int i=0; i<n; ++i)ss[i]=S[i];
	for (int i=0; i<m; ++i)x[i]=X[i], y[i]=Y[i];
	int low=-1, high=m+1;
	while (low+1<high){
		int mid=(low+high)/2;
		if (check(mid))high=mid;
		else low=mid;
	}
	check(high);
	for (int i=0; i<high; ++i)p[i]=ans[i].fi, q[i]=ans[i].se;
	return high;
}

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