Submission #765064

#	Time	Username	Problem	Language	Result	Execution time	Memory
765064		SanguineChameleon	Sorting (IOI15_sorting)	C++17	100 / 100	130 ms	21128 KiB

sorting

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

const int maxN = 2e5 + 20;

int A[maxN];
int B[maxN];
int pos[maxN];
int *S;
int *X;
int *Y;
int *P;
int *Q;
int N, M;

bool check(int K) {
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		pos[A[i]] = i;
		B[i] = i;
	}
	for (int i = K - 1; i >= 0; i--) {
		swap(B[X[i]], B[Y[i]]);
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (pos[B[i]] != i) {
			int x = i;
			int y = pos[B[i]];
			swap(A[x], A[y]);
			swap(pos[A[x]], pos[A[y]]);
			cnt++;
		}
	}
	return cnt <= K;
}

void build(int K) {
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		pos[A[i]] = i;
		B[i] = i;
	}
	for (int i = K - 1; i >= 0; i--) {
		swap(B[X[i]], B[Y[i]]);
	}
	vector<pair<int, int>> swaps;
	for (int i = 0; i < N; i++) {
		if (pos[B[i]] != i) {
			int x = i;
			int y = pos[B[i]];
			swaps.emplace_back(A[x], A[y]);
			swap(A[x], A[y]);
			swap(pos[A[x]], pos[A[y]]);
		}
	}
	swaps.resize(K, make_pair(0, 0));
	for (int i = 0; i < N; i++) {
		pos[S[i]] = i;
	}
	for (int i = 0; i < K; i++) {
		int x = X[i];
		int y = Y[i];
		swap(S[x], S[y]);
		swap(pos[S[x]], pos[S[y]]);
		x = pos[swaps[i].first];
		y = pos[swaps[i].second];
		swap(S[x], S[y]);
		swap(pos[S[x]], pos[S[y]]);
		P[i] = x;
		Q[i] = y;
	}
}

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[]) {
	N = _N;
	S = _S;
	M = _M;
	X = _X;
	Y = _Y;
	P = _P;
	Q = _Q;
	int lt = 0;
	int rt = M;
	int K = -1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			K = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	build(K);
	return K;
}

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