#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);
// cout << v << endl;
for(int u : adj[v]){
// cout << v << ' ' << u << endl;
if(!mark[u]) DFS(u);
}
}
int check(int N, int M, int X[], int Y[]) {
// cout << endl << "==========" << endl << M << endl;
int cnt = 0;
fill(p , p + MAXN , 0);
fill(q , q + MAXN , 0);
fill(mark , mark + MAXN , 0);
for(int i = 0 ; i < N ; i++) adj[i].clear();
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++){
// cout << A[i] << ' ';
adj[i].push_back(A[i]);
}
// cout << endl;
for(int i = 0 ; i < N ; i++){
if(!mark[i]){
vec.clear();
DFS(i);
// cout << "DFS " << i << ' ' << SZ(vec) << endl;
// for(int j : vec) cout << j << ' ';
for(int j = 1 ; j < SZ(vec) ; j++){
if(cnt == M) return 0;
p[cnt] = vec[0];
q[cnt] = vec[j];
// cout << vec[0] << ' ' << vec[j] << endl;
cnt++;
}
// cout << endl;
}
}
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 < N ; i++) A[i] = S[i];
int tmp = check(N , r , X , Y);
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:69:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = l + r >> 1;
| ~~^~~
sorting.cpp:75:6: warning: unused variable 'tmp' [-Wunused-variable]
75 | int tmp = check(N , r , X , Y);
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
7 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7320 KB |
Output is correct |
4 |
Correct |
7 ms |
7404 KB |
Output is correct |
5 |
Correct |
7 ms |
7404 KB |
Output is correct |
6 |
Correct |
7 ms |
7404 KB |
Output is correct |
7 |
Correct |
7 ms |
7404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
7 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7320 KB |
Output is correct |
4 |
Correct |
7 ms |
7404 KB |
Output is correct |
5 |
Correct |
7 ms |
7404 KB |
Output is correct |
6 |
Correct |
7 ms |
7404 KB |
Output is correct |
7 |
Correct |
7 ms |
7404 KB |
Output is correct |
8 |
Correct |
7 ms |
7404 KB |
Output is correct |
9 |
Correct |
7 ms |
7404 KB |
Output is correct |
10 |
Correct |
9 ms |
7404 KB |
Output is correct |
11 |
Correct |
9 ms |
7404 KB |
Output is correct |
12 |
Correct |
9 ms |
7404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
7404 KB |
Output is correct |
2 |
Correct |
8 ms |
7404 KB |
Output is correct |
3 |
Correct |
9 ms |
7404 KB |
Output is correct |
4 |
Correct |
10 ms |
7404 KB |
Output is correct |
5 |
Correct |
10 ms |
7532 KB |
Output is correct |
6 |
Correct |
8 ms |
7404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
7 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7320 KB |
Output is correct |
4 |
Correct |
7 ms |
7404 KB |
Output is correct |
5 |
Correct |
7 ms |
7404 KB |
Output is correct |
6 |
Correct |
7 ms |
7404 KB |
Output is correct |
7 |
Correct |
7 ms |
7404 KB |
Output is correct |
8 |
Correct |
7 ms |
7404 KB |
Output is correct |
9 |
Correct |
7 ms |
7404 KB |
Output is correct |
10 |
Correct |
9 ms |
7404 KB |
Output is correct |
11 |
Correct |
9 ms |
7404 KB |
Output is correct |
12 |
Correct |
9 ms |
7404 KB |
Output is correct |
13 |
Correct |
7 ms |
7404 KB |
Output is correct |
14 |
Correct |
8 ms |
7404 KB |
Output is correct |
15 |
Correct |
9 ms |
7404 KB |
Output is correct |
16 |
Correct |
10 ms |
7404 KB |
Output is correct |
17 |
Correct |
10 ms |
7532 KB |
Output is correct |
18 |
Correct |
8 ms |
7404 KB |
Output is correct |
19 |
Correct |
7 ms |
7404 KB |
Output is correct |
20 |
Correct |
8 ms |
7404 KB |
Output is correct |
21 |
Correct |
11 ms |
7660 KB |
Output is correct |
22 |
Correct |
11 ms |
7660 KB |
Output is correct |
23 |
Correct |
11 ms |
7660 KB |
Output is correct |
24 |
Correct |
12 ms |
7660 KB |
Output is correct |
25 |
Correct |
11 ms |
7660 KB |
Output is correct |
26 |
Correct |
12 ms |
7660 KB |
Output is correct |
27 |
Correct |
11 ms |
7660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7660 KB |
Output is correct |
2 |
Correct |
12 ms |
7660 KB |
Output is correct |
3 |
Correct |
11 ms |
7660 KB |
Output is correct |
4 |
Correct |
10 ms |
7660 KB |
Output is correct |
5 |
Correct |
13 ms |
7660 KB |
Output is correct |
6 |
Correct |
11 ms |
7660 KB |
Output is correct |
7 |
Correct |
11 ms |
7660 KB |
Output is correct |
8 |
Correct |
12 ms |
7660 KB |
Output is correct |
9 |
Correct |
11 ms |
7660 KB |
Output is correct |
10 |
Correct |
11 ms |
7660 KB |
Output is correct |
11 |
Correct |
11 ms |
7680 KB |
Output is correct |
12 |
Correct |
11 ms |
7660 KB |
Output is correct |
13 |
Correct |
11 ms |
7660 KB |
Output is correct |
14 |
Correct |
11 ms |
7532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7660 KB |
Output is correct |
2 |
Correct |
12 ms |
7660 KB |
Output is correct |
3 |
Correct |
11 ms |
7660 KB |
Output is correct |
4 |
Correct |
10 ms |
7660 KB |
Output is correct |
5 |
Correct |
13 ms |
7660 KB |
Output is correct |
6 |
Correct |
11 ms |
7660 KB |
Output is correct |
7 |
Correct |
11 ms |
7660 KB |
Output is correct |
8 |
Correct |
12 ms |
7660 KB |
Output is correct |
9 |
Correct |
11 ms |
7660 KB |
Output is correct |
10 |
Correct |
11 ms |
7660 KB |
Output is correct |
11 |
Correct |
11 ms |
7680 KB |
Output is correct |
12 |
Correct |
11 ms |
7660 KB |
Output is correct |
13 |
Correct |
11 ms |
7660 KB |
Output is correct |
14 |
Correct |
11 ms |
7532 KB |
Output is correct |
15 |
Correct |
821 ms |
31244 KB |
Output is correct |
16 |
Correct |
899 ms |
31680 KB |
Output is correct |
17 |
Execution timed out |
1024 ms |
34272 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |