# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88242 | 2018-12-04T19:02:51 Z | Pajaraja | Sorting (IOI15_sorting) | C++17 | 239 ms | 18716 KB |
#include "sorting.h" #include <bits/stdc++.h> #define MAXN 200007 using namespace std; int s[MAXN],p[MAXN],n,m,x[3*MAXN],y[3*MAXN],pi[MAXN]; bool vi[MAXN]; vector<int> z[2]; void copy() {for(int i=0;i<n;i++) p[i]=s[i];} bool provera(int a) { copy(); int brc=0; for(int r=0;r<a;r++) swap(p[x[r]],p[y[r]]); fill(vi,vi+n,false); for(int i=0;i<n;i++) if(!vi[i]) {brc++; while(!vi[i]) {vi[i]=true; i=p[i];}} return brc+a>=n; } int binarna(int l,int r) { if(l==r) return l; int s=(l+r)/2; if(provera(s)) return binarna(l,s); return binarna(s+1,r); } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; m=M; for(int i=0;i<n;i++) s[i]=S[i]; for(int i=0;i<m;i++) {x[i]=X[i]; y[i]=Y[i];} int r=binarna(0,n); copy(); fill(vi,vi+n,false); for(int i=0;i<r;i++) swap(p[X[i]],p[Y[i]]); for(int i=0;i<n;i++) if(!vi[i]) while(!vi[i]) {vi[i]=true; if(!vi[p[i]]) {z[0].push_back(i); z[1].push_back(p[i]);} i=p[i];} for(int i=0;i<n;i++) pi[S[i]]=i; for(int i=0;i<r;i++) { swap(S[X[i]],S[Y[i]]); pi[S[X[i]]]=X[i]; pi[S[Y[i]]]=Y[i]; if(i>=z[0].size()) P[i]=Q[i]=0; else { if(z[0][i]<z[1][i]) swap(z[0][i],z[1][i]); P[i]=pi[z[0][i]]; Q[i]=pi[z[1][i]]; swap(S[P[i]],S[Q[i]]); pi[S[P[i]]]=P[i]; pi[S[Q[i]]]=Q[i]; } } return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
13 | Correct | 3 ms | 384 KB | Output is correct |
14 | Correct | 3 ms | 384 KB | Output is correct |
15 | Correct | 3 ms | 384 KB | Output is correct |
16 | Correct | 3 ms | 384 KB | Output is correct |
17 | Correct | 3 ms | 384 KB | Output is correct |
18 | Correct | 2 ms | 384 KB | Output is correct |
19 | Correct | 2 ms | 384 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 4 ms | 540 KB | Output is correct |
22 | Correct | 3 ms | 640 KB | Output is correct |
23 | Correct | 3 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 | 4 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 4 ms | 512 KB | Output is correct |
3 | Correct | 3 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 | 0 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 4 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 4 ms | 512 KB | Output is correct |
13 | Correct | 4 ms | 512 KB | Output is correct |
14 | 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 | 4 ms | 512 KB | Output is correct |
3 | Correct | 3 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 | 0 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 4 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 4 ms | 512 KB | Output is correct |
13 | Correct | 4 ms | 512 KB | Output is correct |
14 | Correct | 3 ms | 512 KB | Output is correct |
15 | Correct | 154 ms | 16872 KB | Output is correct |
16 | Correct | 196 ms | 17332 KB | Output is correct |
17 | Correct | 239 ms | 18140 KB | Output is correct |
18 | Correct | 69 ms | 12024 KB | Output is correct |
19 | Correct | 162 ms | 15568 KB | Output is correct |
20 | Correct | 154 ms | 16108 KB | Output is correct |
21 | Correct | 183 ms | 16272 KB | Output is correct |
22 | Correct | 187 ms | 18532 KB | Output is correct |
23 | Correct | 226 ms | 18716 KB | Output is correct |
24 | Correct | 229 ms | 18276 KB | Output is correct |
25 | Correct | 198 ms | 18148 KB | Output is correct |
26 | Correct | 200 ms | 16108 KB | Output is correct |
27 | Correct | 137 ms | 15468 KB | Output is correct |
28 | Correct | 187 ms | 18372 KB | Output is correct |
29 | Correct | 185 ms | 17508 KB | Output is correct |
30 | Correct | 121 ms | 14580 KB | Output is correct |
31 | Correct | 187 ms | 17892 KB | Output is correct |
32 | Correct | 196 ms | 18024 KB | Output is correct |
33 | Correct | 201 ms | 18532 KB | Output is correct |
34 | Correct | 231 ms | 18404 KB | Output is correct |
35 | Correct | 157 ms | 15608 KB | Output is correct |
36 | Correct | 61 ms | 12920 KB | Output is correct |
37 | Correct | 204 ms | 18404 KB | Output is correct |
38 | Correct | 207 ms | 18024 KB | Output is correct |
39 | Correct | 203 ms | 17508 KB | Output is correct |