Submission #58551

#	Time	Username	Problem	Language	Result	Execution time	Memory
58551		ngkan146	Sorting (IOI15_sorting)	C++11	0 / 100	3 ms	512 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 trace(int val,int P[], int Q[]){
	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 = 0;
	for(int i=0;i<n;i++){
		if (b[i] == -1)	continue;
		cnt--;
		int index = i;
		for(int _=0;b[index] != -1;_++){
			int nex = b[index];
			b[index] = -1;
			if (_){
				P[cnt] = index;
				Q[cnt] = nex;
				++cnt;
			}
			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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26