# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
288369 | 2020-09-01T12:53:09 Z | shayan_p | Sorting (IOI15_sorting) | C++17 | 370 ms | 14232 KB |
#include<bits/stdc++.h> #include "sorting.h" #define F first #define S second #define PB push_back #define sz(s) (int(s.size())) #define bit(n, k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef long double ld; const int maxn = 6e5 + 10, mod = 1e9 + 7; bool mark[maxn]; int _p[maxn]; int findSwapPairs(int n, int p[], int q, int a[], int b[], int A[], int B[]){ fill(A, A + q, 0); fill(B, B + q, 0); for(int i = 0; i < n; i++){ _p[ p[i] ] = i; } auto Swap = [&](int i, int j){ swap(p[i], p[j]); _p[ p[i] ] = i, _p[ p[j] ] = j; }; auto need = [&](){ fill(mark, mark + n, 0); int cnt = 0; for(int i = 0; i < n; i++){ int tmp = i; if(!mark[i]){ cnt++; while(!mark[tmp]){ mark[tmp] = 1; tmp = p[tmp]; } } } return n - cnt; }; auto calc_bin = [&](int q){ for(int i = 0; i < q; i++) Swap(a[i], b[i]); int x = need(); for(int i = q-1; i >= 0; i--) Swap(a[i], b[i]); return x <= q; }; auto solve = [&](int q){ fill(mark, mark + n, 0); vector<pii> tdo; for(int i = 0; i < n; i++){ int tmp = i; if(!mark[i]){ int SZ = sz(tdo); while(!mark[tmp]){ if(i != tmp) tdo.PB({i, tmp}); mark[tmp] = 1; tmp = p[tmp]; } reverse(tdo.begin() + SZ, tdo.end()); } } while(sz(tdo)){ q--; int x = tdo.back().F, y = tdo.back().S; tdo.pop_back(); A[q] = _p[x], B[q] = _p[y]; Swap(A[q], B[q]); Swap(a[q], b[q]); } }; int l = -1, r = q; while(r-l > 1){ int mid = (l+r) >> 1; if(calc_bin(mid)) r = mid; else l = mid; } for(int i = 0; i < r; i++){ Swap(a[i], b[i]); } solve(r); return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 0 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 ms | 384 KB | Output is correct |
18 | Correct | 0 ms | 256 KB | Output is correct |
19 | Correct | 0 ms | 384 KB | Output is correct |
20 | Correct | 1 ms | 384 KB | Output is correct |
21 | Correct | 2 ms | 640 KB | Output is correct |
22 | Correct | 2 ms | 512 KB | Output is correct |
23 | Correct | 2 ms | 512 KB | Output is correct |
24 | Correct | 2 ms | 512 KB | Output is correct |
25 | Correct | 2 ms | 512 KB | Output is correct |
26 | Correct | 2 ms | 512 KB | Output is correct |
27 | Correct | 2 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 488 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 512 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 488 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 512 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 236 ms | 12648 KB | Output is correct |
16 | Correct | 245 ms | 12892 KB | Output is correct |
17 | Correct | 325 ms | 13576 KB | Output is correct |
18 | Correct | 88 ms | 10644 KB | Output is correct |
19 | Correct | 234 ms | 12588 KB | Output is correct |
20 | Correct | 248 ms | 12888 KB | Output is correct |
21 | Correct | 247 ms | 13016 KB | Output is correct |
22 | Correct | 270 ms | 13712 KB | Output is correct |
23 | Correct | 264 ms | 14048 KB | Output is correct |
24 | Correct | 296 ms | 13864 KB | Output is correct |
25 | Correct | 321 ms | 13656 KB | Output is correct |
26 | Correct | 230 ms | 12924 KB | Output is correct |
27 | Correct | 209 ms | 12476 KB | Output is correct |
28 | Correct | 315 ms | 13664 KB | Output is correct |
29 | Correct | 291 ms | 13412 KB | Output is correct |
30 | Correct | 170 ms | 12140 KB | Output is correct |
31 | Correct | 269 ms | 13752 KB | Output is correct |
32 | Correct | 273 ms | 13612 KB | Output is correct |
33 | Correct | 345 ms | 13792 KB | Output is correct |
34 | Correct | 298 ms | 13740 KB | Output is correct |
35 | Correct | 241 ms | 12376 KB | Output is correct |
36 | Correct | 67 ms | 11384 KB | Output is correct |
37 | Correct | 353 ms | 14232 KB | Output is correct |
38 | Correct | 344 ms | 13660 KB | Output is correct |
39 | Correct | 370 ms | 13712 KB | Output is correct |