#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define SZ(x) int(x.size())
const int MAXN = 2e5 + 10;
int cnt , to[MAXN] , pos[MAXN] , mark[MAXN];
vector<int> vec , adj[MAXN];
void DFS(int v){
mark[v] = 1;
vec.push_back(v);
for(int u : adj[v]){
if(!mark[u]) DFS(u);
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
for(int i = 0 ; i < N ; i++) to[i] = pos[i] = i;
for(int i = 0 ; i < M ; i++){
swap(S[X[i]] , S[Y[i]]);
}
for(int i = 0 ; i < N ; i++){
adj[i].push_back(S[i]);
// cout << S[i] << ' ';
}
// cout << endl;
for(int i = 0 ; i < N ; i++){
if(!mark[i]){
vec.clear();
DFS(i);
for(int j = 1 ; j < SZ(vec) ; j++){
P[cnt] = vec[0];
Q[cnt] = vec[j];
cnt++;
}
}
}
for(int i = M - 1 ; i >= 0 ; i--){
if(i < cnt){
P[i] = to[P[i]];
Q[i] = to[Q[i]];
}
to[pos[X[i]]] = Y[i];
to[pos[Y[i]]] = X[i];
swap(pos[X[i]] , pos[Y[i]]);
}
return cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
4 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
4 ms |
5248 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
4 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
4 ms |
5248 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
4972 KB |
Output is correct |
14 |
Correct |
4 ms |
4972 KB |
Output is correct |
15 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |