# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
615558 |
2022-07-31T10:37:41 Z |
Lucpp |
Sorting (IOI15_sorting) |
C++17 |
|
477 ms |
21784 KB |
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, vector<int> a, vector<int> ainv, int m, int X[], int Y[], int P[], int Q[]){
vector<int> p(n), pinv(n);
for(int i = 0; i < n; i++) p[i] = pinv[i] = i;
for(int i = 0; i < m; i++){
swap(p[pinv[X[i]]], p[pinv[Y[i]]]);
swap(pinv[X[i]], pinv[Y[i]]);
}
int cur = 0;
for(int i = 0; i < m; i++){
swap(p[X[i]], p[Y[i]]);
swap(pinv[p[X[i]]], pinv[p[Y[i]]]);
swap(a[X[i]], a[Y[i]]);
swap(ainv[a[X[i]]], ainv[a[Y[i]]]);
P[i] = Q[i] = 0;
while(cur < n && cur == p[ainv[cur]]) cur++;
if(cur < n){
P[i] = ainv[cur];
Q[i] = pinv[cur];
swap(a[P[i]], a[Q[i]]);
swap(ainv[a[P[i]]], ainv[a[Q[i]]]);
}
}
for(int i = 0; i < n; i++) if(a[i] != i) return false;
return true;
}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> a(n), ainv(n);
for(int i = 0; i < n; i++) a[i] = S[i], ainv[S[i]] = i;
int lo = 0, hi = M-1;
for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
if(solve(n, a, ainv, mid, X, Y, P, Q)) hi = mid;
else lo = mid+1;
}
solve(n, a, ainv, lo, X, Y, P, Q);
return lo;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
304 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
2 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
552 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
2 ms |
568 KB |
Output is correct |
27 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
440 KB |
Output is correct |
6 |
Correct |
1 ms |
436 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
440 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
440 KB |
Output is correct |
6 |
Correct |
1 ms |
436 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
440 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
298 ms |
19028 KB |
Output is correct |
16 |
Correct |
361 ms |
19668 KB |
Output is correct |
17 |
Correct |
461 ms |
20684 KB |
Output is correct |
18 |
Correct |
111 ms |
20048 KB |
Output is correct |
19 |
Correct |
292 ms |
21156 KB |
Output is correct |
20 |
Correct |
294 ms |
21672 KB |
Output is correct |
21 |
Correct |
294 ms |
21784 KB |
Output is correct |
22 |
Correct |
297 ms |
16048 KB |
Output is correct |
23 |
Correct |
339 ms |
21324 KB |
Output is correct |
24 |
Correct |
477 ms |
21012 KB |
Output is correct |
25 |
Correct |
437 ms |
20732 KB |
Output is correct |
26 |
Correct |
306 ms |
21656 KB |
Output is correct |
27 |
Correct |
257 ms |
21312 KB |
Output is correct |
28 |
Correct |
430 ms |
21144 KB |
Output is correct |
29 |
Correct |
420 ms |
20984 KB |
Output is correct |
30 |
Correct |
201 ms |
21336 KB |
Output is correct |
31 |
Correct |
435 ms |
21332 KB |
Output is correct |
32 |
Correct |
354 ms |
20600 KB |
Output is correct |
33 |
Correct |
457 ms |
21056 KB |
Output is correct |
34 |
Correct |
411 ms |
20944 KB |
Output is correct |
35 |
Correct |
300 ms |
20740 KB |
Output is correct |
36 |
Correct |
88 ms |
21360 KB |
Output is correct |
37 |
Correct |
473 ms |
21724 KB |
Output is correct |
38 |
Correct |
468 ms |
20748 KB |
Output is correct |
39 |
Correct |
435 ms |
20892 KB |
Output is correct |