Submission #615558

#	Time	Username	Problem	Language	Result	Execution time	Memory
615558		Lucpp	Sorting (IOI15_sorting)	C++17	100 / 100	477 ms	21784 KiB

sorting

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

bool solve(int n, vector<int> a, vector<int> ainv, int m, int X[], int Y[], int P[], int Q[]){
	vector<int> p(n), pinv(n);
	for(int i = 0; i < n; i++) p[i] = pinv[i] = i;
	for(int i = 0; i < m; i++){
		swap(p[pinv[X[i]]], p[pinv[Y[i]]]);
		swap(pinv[X[i]], pinv[Y[i]]);
	}
	int cur = 0;
	for(int i = 0; i < m; i++){
		swap(p[X[i]], p[Y[i]]);
		swap(pinv[p[X[i]]], pinv[p[Y[i]]]);
		swap(a[X[i]], a[Y[i]]);
		swap(ainv[a[X[i]]], ainv[a[Y[i]]]);
		P[i] = Q[i] = 0;
		while(cur < n && cur == p[ainv[cur]]) cur++;
		if(cur < n){
			P[i] = ainv[cur];
			Q[i] = pinv[cur];
			swap(a[P[i]], a[Q[i]]);
			swap(ainv[a[P[i]]], ainv[a[Q[i]]]);
		}
	}
	for(int i = 0; i < n; i++) if(a[i] != i) return false;
	return true;
}

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int> a(n), ainv(n);
	for(int i = 0; i < n; i++) a[i] = S[i], ainv[S[i]] = i;
	int lo = 0, hi = M-1;
	for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
		if(solve(n, a, ainv, mid, X, Y, P, Q)) hi = mid;
		else lo = mid+1;
	}
	solve(n, a, ainv, lo, X, Y, P, Q);
	return lo;
}

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