Submission #52856

#	Time	Username	Problem	Language	Result	Execution time	Memory
52856		tmwilliamlin168	Sorting (IOI15_sorting)	C++14	100 / 100	214 ms	11640 KiB

sorting

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

const int mxN=2e5;
int a[mxN], b[mxN];
bool vis[mxN];

int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
	int lb=0, rb=n-1, mb, ss;
	while(lb<=rb) {
		mb=(lb+rb)/2, ss=0;
		memcpy(a, s, 4*n);
		for(int i=0; i<mb; ++i)
			swap(a[x[i]], a[y[i]]);
		memset(vis, 0, n);
		for(int i=0; i<n; ++i) {
			if(vis[i])
				continue;
			vis[i]=1;
			for(int j=i; !vis[a[j]]; j=a[j]) {
				vis[a[j]]=1;
				++ss;
			}
		}
		if(ss<=mb)
			rb=mb-1;
		else
			lb=mb+1;
	}
	ss=0;
	memcpy(a, s, 4*n);
	for(int i=0; i<lb; ++i)
		swap(a[x[i]], a[y[i]]);
//	for(int i=0; i<n; ++i)
//		cout << a[i] << " ";
//	cout << endl;
	memset(vis, 0, n);
	for(int i=0; i<n; ++i)
		b[s[i]]=i;
	for(int i=0; i<n; ++i) {
		if(vis[i])
			continue;
		vis[i]=1;
		for(int j=i; !vis[a[j]]; j=a[j]) {
			vis[a[j]]=1;
			swap(s[x[ss]], s[y[ss]]);
			b[s[x[ss]]]=x[ss];
			b[s[y[ss]]]=y[ss];
			p[ss]=b[a[j]];
			q[ss]=b[a[a[j]]];
			swap(s[p[ss]], s[q[ss]]);
			b[s[p[ss]]]=p[ss];
			b[s[q[ss]]]=q[ss];
			++ss;
		}
	}
	memset(p+ss, 0, 4*(lb-ss));
	memset(q+ss, 0, 4*(lb-ss));
	return lb;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:9:38: warning: unused parameter 'm' [-Wunused-parameter]
 int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
                                      ^

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