Submission #58555

#	Time	Username	Problem	Language	Result	Execution time	Memory
58555		ngkan146	Sorting (IOI15_sorting)	C++11	100 / 100	266 ms	17016 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200000], b[200000];
int m;
int x[600000], y[600000];

bool check(int val){
	for(int i=0;i<n;i++)
		b[i] = a[i];
		
	for(int i=0;i<val;i++)
		swap(b[x[i]], b[y[i]]);
		
	int cnt = n;
	for(int i=0;i<n;i++){
		if (b[i] == -1)	continue;
		cnt--;
		int index = i;
		do{
			int nex = b[index];
			b[index] = -1;
			index = nex;
		}while(index != i);
	}
	
	return cnt <= val;
}
int curPos[200000];
int trace(int val,int P[], int Q[]){
	for(int i=0;i<n;i++)
		b[i] = a[i],
		curPos[a[i]] = i;
		
	for(int i=0;i<val;i++)
		swap(b[x[i]], b[y[i]]);

	int cnt = 0;
	for(int i=0;i<n;i++){
		if (b[i] == -1)	continue;
		
		int index = i;
		for(int _=0;b[index] != -1;_++){
			int nex = b[index];
			if (nex == i)	{b[index] = -1; break;}
			//~ cout << index << ' ' << nex << endl;
			
			swap(curPos[a[x[cnt]]], curPos[a[y[cnt]]]);
			swap(a[x[cnt]], a[y[cnt]]);
			
			//~ for(int j=0;j<n;j++)	cout << a[j] << ' '; cout << endl;
			
			P[cnt] = curPos[b[index]];
			Q[cnt] = curPos[b[nex]];
			
			swap(curPos[a[P[cnt]]], curPos[a[Q[cnt]]]);
			swap(a[P[cnt]], a[Q[cnt]]);
			++cnt;
			
			//~ for(int j=0;j<n;j++)	cout << a[j] << ' '; cout << endl;
			
			b[index] = -1;
			index = nex;
		}
	}
	
	while(cnt < val)	P[cnt] = Q[cnt] = 0, ++cnt;
	return val;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	for(int i=0;i<n;i++)
		a[i] = S[i];
	m = M;
	for(int i=0;i<m;i++)
		x[i] = X[i],
		y[i] = Y[i];
	
	int l=-1, r=m;
	while(l+1<r){
		int mid = (l+r)/2;
		if (check(mid))	r = mid;
		else l = mid;
	}
	return trace(r,P,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