제출 #32168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32168		imeimi2000	정렬하기 (IOI15_sorting)	C++14	100 / 100	226 ms	14900 KiB

sorting

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

using namespace std;
typedef long long llong;

int arr[200000];
int x[200000];
int y[200000];
int n, m;
int tmp[200000];
bool ch[200000];
int ps[200000];
int qs[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 = m = N;
	for (int i = 0; i < n; ++i) arr[i] = S[i];
	for (int i = 0; i < m; ++i) x[i] = X[i], y[i] = Y[i];
	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) ps[i] = qs[i] = 0;
		}
		ps[i] = tmp[j]; qs[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 = ps[i], q = qs[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;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:30:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^

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