#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,*a,m,*x,*y,r;
bool C(int k){
int p[200000],ans = 0;
bool used[200000] = {};
for(int i = 0;i < n;i++) p[i] = a[i];
for(int i = 0;i < k;i++) swap(p[x[i]],p[y[i]]);
for(int i = 0;i < n;i++){
if(!used[i]){
int pos = i;
while(!used[pos]){
ans++;
used[pos] = true;
pos = p[pos];
}
ans--;
}
}
return ans <= k;
}
typedef pair<int,int> pii;
int b[200000];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;a = S;m = M;x = X;y = Y;
int low = -1,up = m;
while(up - low > 1){
int mid = (up + low) / 2;
if(C(mid)) up = mid;
else low = mid;
}
r = up;
vector<pii> vec;
int p[200000];
bool used[200000] = {};
for(int i = 0;i < n;i++) p[i] = a[i];
for(int i = 0;i < r;i++) swap(p[x[i]],p[y[i]]);
for(int i = 0;i < n;i++) b[p[i]] = i;
for(int i = 0;i < n;i++){
if(b[i] != i){
int c = i,d = b[i];
vec.pb(pii(p[c],p[d]));
swap(p[c],p[d]);
swap(b[p[c]],b[p[d]]);
}
}
for(int i = 0;i < n;i++) b[S[i]] = i;
for(int i = 0;i < r;i++){
swap(S[x[i]],S[y[i]]);
swap(b[S[x[i]]],b[S[y[i]]]);
if(i < vec.size()){
P[i] = b[vec[i].first];
Q[i] = b[vec[i].second];
swap(S[P[i]],S[Q[i]]);
swap(b[S[P[i]]],b[S[Q[i]]]);
}else{
P[i] = 0;
Q[i] = 0;
}
}
return r;
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:57:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < vec.size()){
~~^~~~~~~~~~~~
sorting.cpp:41:7: warning: unused variable 'used' [-Wunused-variable]
bool used[200000] = {};
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
512 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
512 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
512 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
512 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
512 KB |
Output is correct |
| 13 |
Correct |
2 ms |
540 KB |
Output is correct |
| 14 |
Correct |
3 ms |
512 KB |
Output is correct |
| 15 |
Correct |
2 ms |
512 KB |
Output is correct |
| 16 |
Correct |
2 ms |
640 KB |
Output is correct |
| 17 |
Correct |
3 ms |
640 KB |
Output is correct |
| 18 |
Correct |
2 ms |
512 KB |
Output is correct |
| 19 |
Correct |
3 ms |
512 KB |
Output is correct |
| 20 |
Correct |
3 ms |
512 KB |
Output is correct |
| 21 |
Correct |
4 ms |
640 KB |
Output is correct |
| 22 |
Correct |
4 ms |
640 KB |
Output is correct |
| 23 |
Correct |
4 ms |
640 KB |
Output is correct |
| 24 |
Correct |
3 ms |
640 KB |
Output is correct |
| 25 |
Correct |
3 ms |
640 KB |
Output is correct |
| 26 |
Correct |
3 ms |
640 KB |
Output is correct |
| 27 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
612 KB |
Output is correct |
| 2 |
Correct |
4 ms |
640 KB |
Output is correct |
| 3 |
Correct |
3 ms |
640 KB |
Output is correct |
| 4 |
Correct |
3 ms |
640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
640 KB |
Output is correct |
| 6 |
Correct |
4 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
4 ms |
640 KB |
Output is correct |
| 12 |
Correct |
3 ms |
640 KB |
Output is correct |
| 13 |
Correct |
4 ms |
640 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
612 KB |
Output is correct |
| 2 |
Correct |
4 ms |
640 KB |
Output is correct |
| 3 |
Correct |
3 ms |
640 KB |
Output is correct |
| 4 |
Correct |
3 ms |
640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
640 KB |
Output is correct |
| 6 |
Correct |
4 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
4 ms |
640 KB |
Output is correct |
| 12 |
Correct |
3 ms |
640 KB |
Output is correct |
| 13 |
Correct |
4 ms |
640 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| 15 |
Correct |
167 ms |
11264 KB |
Output is correct |
| 16 |
Correct |
193 ms |
11448 KB |
Output is correct |
| 17 |
Correct |
270 ms |
12092 KB |
Output is correct |
| 18 |
Correct |
70 ms |
7800 KB |
Output is correct |
| 19 |
Correct |
161 ms |
10124 KB |
Output is correct |
| 20 |
Correct |
182 ms |
10616 KB |
Output is correct |
| 21 |
Correct |
150 ms |
10636 KB |
Output is correct |
| 22 |
Correct |
200 ms |
12280 KB |
Output is correct |
| 23 |
Correct |
200 ms |
12636 KB |
Output is correct |
| 24 |
Correct |
219 ms |
12244 KB |
Output is correct |
| 25 |
Correct |
220 ms |
12292 KB |
Output is correct |
| 26 |
Correct |
178 ms |
10580 KB |
Output is correct |
| 27 |
Correct |
152 ms |
10096 KB |
Output is correct |
| 28 |
Correct |
228 ms |
12088 KB |
Output is correct |
| 29 |
Correct |
196 ms |
11620 KB |
Output is correct |
| 30 |
Correct |
94 ms |
9456 KB |
Output is correct |
| 31 |
Correct |
208 ms |
11832 KB |
Output is correct |
| 32 |
Correct |
191 ms |
12172 KB |
Output is correct |
| 33 |
Correct |
230 ms |
12364 KB |
Output is correct |
| 34 |
Correct |
198 ms |
12284 KB |
Output is correct |
| 35 |
Correct |
176 ms |
10236 KB |
Output is correct |
| 36 |
Correct |
51 ms |
8312 KB |
Output is correct |
| 37 |
Correct |
229 ms |
12612 KB |
Output is correct |
| 38 |
Correct |
231 ms |
12160 KB |
Output is correct |
| 39 |
Correct |
194 ms |
12152 KB |
Output is correct |
