제출 #32167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32167		imeimi2000	Sorting (IOI15_sorting)	C++14	8 / 100	97 ms	640 KiB

sorting

#include "sorting.h"
#include <vector>
#include <algorithm>

using namespace std;
typedef long long llong;

int arr[200000];
int * x;
int * y;
int n, m;
int tmp[200000];
bool ch[200000];

bool check(int r) {
	int j, cnt = 0;
	for (int i = 0; i < n; ++i) tmp[i] = arr[i], ch[i] = false;
	for (int i = 0; i < r; ++i) swap(tmp[x[i]], tmp[y[i]]);
	for (int i = 0; i < n; ++i) {
		if (ch[i]) continue;
		ch[i] = true;
		j = tmp[i];
		while (j != i) ++cnt, ch[j] = true, j = tmp[j];
	}
	return cnt <= r;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	for (int i = 0; i < n; ++i) arr[i] = S[i];
	x = X;
	y = Y;
	int s = 0, e = m;
	while (s < e) {
		int t = (s + e) / 2;
		if (check(t)) e = t;
		else s = t + 1;
	}
	for (int i = 0; i < n; ++i) tmp[i] = arr[i];
	for (int i = 0; i < s; ++i) {
		swap(tmp[x[i]], tmp[y[i]]);
	}
	for (int i = 0, j = 0; i < m; ++i) {
		while (j < n && tmp[j] == j) ++j;
		if (j == n) {
			for (; i < m; ++i) P[i] = Q[i] = 0;
		}
		P[i] = tmp[j]; Q[i] = tmp[tmp[j]];
		swap(tmp[j], tmp[tmp[j]]);
	}
	for (int i = 0; i < n; ++i) tmp[arr[i]] = i;
	for (int i = 0; i < s; ++i) {
		int p = P[i], q = Q[i];
		swap(tmp[arr[x[i]]], tmp[arr[y[i]]]);
		swap(arr[x[i]], arr[y[i]]);
		P[i] = tmp[p];
		Q[i] = tmp[q];
		swap(arr[tmp[p]], arr[tmp[q]]);
		swap(tmp[p], tmp[q]);
	}
	return s;
}

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