#include <bits/stdc++.h>
#include "sorting.h"
//#include "grader.cpp"
using namespace std;
const int nn = (int)1e6 + 7;
int x[nn], y[nn], p[nn], q[nn], n, s[nn], m;
int pos[nn], pos1[nn], p1[nn], p2[nn];
void upd(int a, int b) {
swap(p1[a], p1[b]);
p2[p1[a]] = a;
p2[p1[b]] = b;
}
void upd1(int a, int b) {
swap(pos[a], pos[b]);
pos1[pos[a]] = a;
pos1[pos[b]] = b;
}
bool check(int val) {
iota(pos, pos + n, 0);
iota(p1, p1 + n, 0);
for (int i = 0; i < val; i++) {
swap(pos[x[i]], pos[y[i]]);
}
for (int i = 0; i < n; i++) {
p2[p1[i]] = i;
pos1[pos[i]] = i;
}
bool fl = 0;
int cur = 0;
for (int i = val - 1; i >= 0; i--) {
int ppos = pos1[cur];
if (s[cur] != p1[ppos]) {
upd(p2[s[cur]], ppos);
}
cur++;
upd(x[i], y[i]);
upd1(x[i], y[i]);
}
for (int i = 0; i < n; i++) {
int ppos = pos1[i];
if (s[i] != p1[ppos]) return 0;
}
return 1;
}
int asd;
void make(int val) {
iota(pos, pos + n, 0);
iota(p1, p1 + n, 0);
for (int i = 0; i < val; i++) {
swap(pos[x[i]], pos[y[i]]);
}
for (int i = 0; i < n; i++) {
p2[p1[i]] = i;
pos1[pos[i]] = i;
}
bool fl = 0;
int cur = 0;
asd = val - 1;;
for (int i = val - 1; i >= 0; i--) {
int ppos = pos1[cur];
if (s[cur] != p1[ppos]) {
p[asd] = p2[s[cur]];
q[asd--] = ppos;
upd(p2[s[cur]], ppos);
}
cur++;
upd(x[i], y[i]);
upd1(x[i], y[i]);
}
}
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++)
s[i] = S[i];
for (int i = 0; i < m; i++) {
x[i] = X[i]; y[i] = Y[i];
}
int l = 0;
int r = n + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
if (check(l)) r = l;
make(r);
for (int i = 0; i <= asd; i++) {
P[i] = 0;
Q[i] = 0;
}
for (int i = asd; i < r; i++) {
P[i] = p[i];
Q[i] = q[i];
}
return r;
}
//main() {
// int n;
// cin >> n;
// int S[n];
// for (int i = 0; i < n; i++) {
// cin >> S[i];
// }
// int m;
// cin >> m;
// int X[M], Y[M];
// for (int i = 0; i < m; i++) {
// cin >> X[i] >> Y[i];
// }
// int ans1[M], ans2[M];
// int sz = findSwapPairs(n, S, m, X, Y, ans1, ans2);
// cout << sz << endl;
// for (int i = 0; i < sz; i++) {
// cout << ans1[i] << ' ' << ans2[i] << endl;
// }
//}
Compilation message
sorting.cpp: In function 'bool check(int)':
sorting.cpp:34:8: warning: unused variable 'fl' [-Wunused-variable]
bool fl = 0;
^~
sorting.cpp: In function 'void make(int)':
sorting.cpp:64:8: warning: unused variable 'fl' [-Wunused-variable]
bool fl = 0;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |