# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789737 | 2023-07-21T22:04:27 Z | I_Love_EliskaM_ | Sorting (IOI15_sorting) | C++14 | 106 ms | 21728 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define pi pair<int,int> #define f first #define s second int findSwapPairs(int n, int _p[], int m, int x[], int y[], int P[], int Q[]) { int z=1; forn(i,n) if (_p[i]!=i) z=0; if (z) return 0; int l=1, r=n; while (l<r) { int m=(l+r)>>1; vector<int> p(n); forn(i,n) p[i]=_p[i]; forn(i,m) { swap(p[x[i]],p[y[i]]); } vector<int> pos(n); forn(i,n) pos[p[i]]=i; int z=0; forn(i,n) { if (p[i]!=i) { z++; pos[p[i]]=pos[i]; swap(p[pos[i]],p[i]); } } if (z<=m) r=m; else l=m+1; } for (int k=r; k<=m; ++k) { vector<int> p(n); forn(i,n) p[i]=_p[i]; auto a=p; forn(i,k) { swap(p[x[i]],p[y[i]]); } vector<int> pos(n); forn(i,n) pos[p[i]]=i; vector<pi> v; forn(i,n) { if (p[i]!=i) { v.pb({i,p[i]}); pos[p[i]]=pos[i]; swap(p[pos[i]],p[i]); } } if (v.size()<=k) { while (v.size()<k) v.pb({0,0}); forn(i,n) pos[a[i]]=i; vector<pi> e; forn(i,k) { swap(pos[a[x[i]]],pos[a[y[i]]]); swap(a[x[i]],a[y[i]]); e.pb({pos[v[i].f],pos[v[i].s]}); swap(pos[v[i].f],pos[v[i].s]); swap(a[pos[v[i].f]],a[pos[v[i].s]]); } forn(i,k) P[i]=e[i].f, Q[i]=e[i].s; return k; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 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 | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 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 | 340 KB | Output is correct |
6 | Correct | 0 ms | 296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 0 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 | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 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 | 340 KB | Output is correct |
18 | Correct | 0 ms | 296 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 468 KB | Output is correct |
22 | Correct | 2 ms | 452 KB | Output is correct |
23 | Correct | 1 ms | 468 KB | Output is correct |
24 | Correct | 1 ms | 468 KB | Output is correct |
25 | Correct | 1 ms | 428 KB | Output is correct |
26 | Correct | 1 ms | 436 KB | Output is correct |
27 | Correct | 1 ms | 412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 440 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 440 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 2 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 480 KB | Output is correct |
13 | Correct | 2 ms | 496 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 440 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 440 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 2 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 480 KB | Output is correct |
13 | Correct | 2 ms | 496 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 78 ms | 19312 KB | Output is correct |
16 | Correct | 83 ms | 19716 KB | Output is correct |
17 | Correct | 106 ms | 20640 KB | Output is correct |
18 | Correct | 35 ms | 13396 KB | Output is correct |
19 | Correct | 79 ms | 19672 KB | Output is correct |
20 | Correct | 83 ms | 20296 KB | Output is correct |
21 | Correct | 95 ms | 20380 KB | Output is correct |
22 | Correct | 67 ms | 15952 KB | Output is correct |
23 | Correct | 96 ms | 21384 KB | Output is correct |
24 | Correct | 106 ms | 21184 KB | Output is correct |
25 | Correct | 93 ms | 20884 KB | Output is correct |
26 | Correct | 86 ms | 20316 KB | Output is correct |
27 | Correct | 78 ms | 19592 KB | Output is correct |
28 | Correct | 90 ms | 21000 KB | Output is correct |
29 | Correct | 89 ms | 20684 KB | Output is correct |
30 | Correct | 73 ms | 18432 KB | Output is correct |
31 | Correct | 97 ms | 20988 KB | Output is correct |
32 | Correct | 88 ms | 20692 KB | Output is correct |
33 | Correct | 94 ms | 21136 KB | Output is correct |
34 | Correct | 91 ms | 21068 KB | Output is correct |
35 | Correct | 81 ms | 19544 KB | Output is correct |
36 | Correct | 50 ms | 16636 KB | Output is correct |
37 | Correct | 98 ms | 21728 KB | Output is correct |
38 | Correct | 92 ms | 20824 KB | Output is correct |
39 | Correct | 101 ms | 20948 KB | Output is correct |