Submission #765056

#	Time	Username	Problem	Language	Result	Execution time	Memory
765056		SanguineChameleon	Sorting (IOI15_sorting)	C++17	0 / 100	1 ms	468 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(A[x], A[y]);
		swap(pos[A[x]], pos[A[y]]);
		x = pos[swaps[i].first];
		y = pos[swaps[i].second];
		swap(A[x], A[y]);
		swap(pos[A[x]], pos[A[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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26