# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
433058 | timmyfeng | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "sorting.h"
const int N = 200000;
int perm[N], inv[N], first[N], second[N];
bool visited[N];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int low = 0, high = M + 1;
while (low < high) {
int mid = (low + high) / 2;
copy(S, S + N, perm);
for (int i = 0; i < mid; ++i) {
swap(perm[X[i]], perm[Y[i]]);
}
int count = 0;
fill(visited, visited + N, false);
fill(first, first + N, 0);
fill(second, second + N, 0);
for (int i = 0; i < N; ++i) {
while (perm[i] != i) {
first[count] = perm[i], second[count] = perm[perm[i]], ++count;
swap(perm[i], perm[perm[i]]);
}
}
if (count <= mid) {
high = mid;
copy(S, S + N, perm);
for (int i = 0; i < N; ++i) {
inv[perm[i]] = i;
}
for (int i = 0; i < mid; ++i) {
swap(perm[X[i]], perm[Y[i]]);
swap(inv[perm[X[i]]], inv[perm[Y[i]]]);
P[i] = first[i], Q[i] = second[i];
swap(inv[P[i]], inv[Q[i]]);
P[i] = inv[P[i]], Q[i] = inv[Q[i]];
swap(perm[P[i]], perm[Q[i]]);
}
} else {
low = mid + 1;
}
}
return low;
}