#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define SZ(x) int(x.size())
const int MAXN = 2e5 + 10;
int A[MAXN] , to[MAXN] , pos[MAXN] , mark[MAXN] , p[MAXN] , q[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 check(int N, int M, int X[], int Y[]) {
int cnt = 0;
fill(p , p + MAXN , 0);
fill(q , q + MAXN , 0);
fill(mark , mark + MAXN , 0);
fill(adj , adj + MAXN , vector<int>());
for(int i = 0 ; i < N ; i++) to[i] = pos[i] = i;
for(int i = 0 ; i < M ; i++){
swap(A[X[i]] , A[Y[i]]);
}
for(int i = 0 ; i < N ; i++){
adj[i].push_back(A[i]);
}
for(int i = 0 ; i < N ; i++){
if(!mark[i]){
vec.clear();
DFS(i);
for(int j = 1 ; j < SZ(vec) ; j++){
if(cnt == M) return 0;
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 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int l = -1 , r = M;
while(r - l > 1){
int mid = l + r >> 1;
for(int i = 0 ; i < N ; i++) A[i] = S[i];
if(check(N , mid , X , Y)) r = mid;
else l = mid;
}
for(int i = 0 ; i < r ; i++){
P[i] = p[i];
Q[i] = q[i];
}
return r;
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
9 ms |
7404 KB |
Output is correct |
3 |
Incorrect |
8 ms |
7404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
9 ms |
7404 KB |
Output is correct |
3 |
Incorrect |
8 ms |
7404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
7404 KB |
Output is correct |
2 |
Correct |
15 ms |
7404 KB |
Output is correct |
3 |
Incorrect |
20 ms |
7404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
9 ms |
7404 KB |
Output is correct |
3 |
Incorrect |
8 ms |
7404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
7660 KB |
Output is correct |
2 |
Correct |
25 ms |
7660 KB |
Output is correct |
3 |
Incorrect |
24 ms |
7660 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
7660 KB |
Output is correct |
2 |
Correct |
25 ms |
7660 KB |
Output is correct |
3 |
Incorrect |
24 ms |
7660 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |