#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
284 KB |
Output is correct |
6 |
Correct |
3 ms |
256 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
284 KB |
Output is correct |
6 |
Correct |
3 ms |
256 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
356 KB |
Output is correct |
2 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
284 KB |
Output is correct |
6 |
Correct |
3 ms |
256 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Runtime error |
97 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Runtime error |
97 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |