# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70140 | 2018-08-22T11:46:27 Z | Vahan | Sorting (IOI15_sorting) | C++17 | 187 ms | 16432 KB |
#include "sorting.h" #include<algorithm> #include<vector> #include<iostream> using namespace std; vector<pair<int,int> > v; int n,ps[300000],s[300000],x[300000],y[300000],rev_ps[300000],r[300000]; int qayl_qan() { int q=0; for(int i=0;i<n;i++) rev_ps[ps[i]]=i; for(int i=0;i<n;i++) { if(ps[rev_ps[i]]==ps[i]) continue; int e=ps[i]; swap(ps[rev_ps[i]],ps[i]); q++; swap(rev_ps[i],rev_ps[e]); } return q; } int stug(int e) { for(int i=0;i<n;i++) ps[i]=s[i]; for(int i=0;i<=e;i++) swap(ps[x[i]],ps[y[i]]); if(qayl_qan()<=e+1) return 1; else return 0; } int bin(int l,int r) { if(l==r) return r; int mid=(l+r)/2; if(stug(mid)) bin(l,mid); else bin(mid+1,r); } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { if(M>=N) M=N-1; 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]; } n=N; for(int i=0;i<n;i++) ps[i]=s[i]; if(qayl_qan()==0) return 0; int t=bin(0,M-1); t++; for(int i=0;i<n;i++) ps[i]=s[i]; for(int i=0;i<t;i++) swap(ps[x[i]],ps[y[i]]); for(int i=0;i<n;i++) rev_ps[ps[i]]=i; for(int i=0;i<n;i++) { if(ps[rev_ps[i]]==ps[i]) continue; int e=ps[i]; swap(ps[rev_ps[i]],ps[i]); v.push_back({ps[i],e}); swap(rev_ps[i],rev_ps[e]); } for(int i=0;i<n;i++) r[s[i]]=i; for(int i=0;i<t;i++) { swap(s[x[i]],s[y[i]]); swap(r[s[x[i]]],r[s[y[i]]]); if(v.size()>i) { P[i]=r[v[i].first]; Q[i]=r[v[i].second]; } else { P[i]=0; Q[i]=0; } swap(s[P[i]],s[Q[i]]); swap(r[s[P[i]]],r[s[Q[i]]]); } return t; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 3 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 3 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 3 ms | 356 KB | Output is correct |
12 | 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 | 2 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 412 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 | 3 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 3 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 3 ms | 356 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
13 | Correct | 2 ms | 384 KB | Output is correct |
14 | Correct | 2 ms | 384 KB | Output is correct |
15 | Correct | 3 ms | 384 KB | Output is correct |
16 | Correct | 2 ms | 412 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 | 3 ms | 484 KB | Output is correct |
22 | Correct | 3 ms | 512 KB | Output is correct |
23 | Correct | 4 ms | 512 KB | Output is correct |
24 | Correct | 3 ms | 484 KB | Output is correct |
25 | Correct | 3 ms | 512 KB | Output is correct |
26 | Correct | 4 ms | 512 KB | Output is correct |
27 | Correct | 4 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 | 3 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 4 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 | 4 ms | 512 KB | Output is correct |
11 | Correct | 4 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 512 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 3 ms | 484 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 | 3 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 4 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 | 4 ms | 512 KB | Output is correct |
11 | Correct | 4 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 512 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 3 ms | 484 KB | Output is correct |
15 | Correct | 126 ms | 14708 KB | Output is correct |
16 | Correct | 111 ms | 14824 KB | Output is correct |
17 | Correct | 165 ms | 15736 KB | Output is correct |
18 | Correct | 42 ms | 8952 KB | Output is correct |
19 | Correct | 169 ms | 13044 KB | Output is correct |
20 | Correct | 153 ms | 13528 KB | Output is correct |
21 | Correct | 157 ms | 13644 KB | Output is correct |
22 | Correct | 120 ms | 15892 KB | Output is correct |
23 | Correct | 129 ms | 16156 KB | Output is correct |
24 | Correct | 187 ms | 15964 KB | Output is correct |
25 | Correct | 145 ms | 15764 KB | Output is correct |
26 | Correct | 149 ms | 13520 KB | Output is correct |
27 | Correct | 148 ms | 13036 KB | Output is correct |
28 | Correct | 172 ms | 15712 KB | Output is correct |
29 | Correct | 173 ms | 15080 KB | Output is correct |
30 | Correct | 112 ms | 12064 KB | Output is correct |
31 | Correct | 182 ms | 15436 KB | Output is correct |
32 | Correct | 143 ms | 15720 KB | Output is correct |
33 | Correct | 172 ms | 15932 KB | Output is correct |
34 | Correct | 154 ms | 15976 KB | Output is correct |
35 | Correct | 147 ms | 13036 KB | Output is correct |
36 | Correct | 51 ms | 10492 KB | Output is correct |
37 | Correct | 180 ms | 16432 KB | Output is correct |
38 | Correct | 170 ms | 15720 KB | Output is correct |
39 | Correct | 168 ms | 15848 KB | Output is correct |