| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131716 |
2019-07-17T13:20:42 Z |
nxteru |
Sorting (IOI15_sorting) |
C++14 |
|
230 ms |
25580 KB |
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,s[200005],x[600005],y[600005],t[200005],a[200005];
bool vis[200005];
bool check(int p){
for(int i=0;i<n;i++)t[i]=s[i];
for(int i=0;i<p;i++)swap(t[x[i]],t[y[i]]);
int cnt=n;
for(int i=0;i<n;i++)vis[i]=false;
for(int i=0;i<n;i++){
int v=i;
if(!vis[i])cnt--;
while(!vis[v]){
vis[v]=true;
v=t[v];
}
}
return cnt<=p;
}
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 l=-1,r=n;
while(r-l>1){
int o=(l+r)/2;
if(check(o))r=o;
else l=o;
}
for(int i=0;i<n;i++)t[i]=s[i];
for(int i=0;i<r;i++)swap(t[x[i]],t[y[i]]);
for(int i=0;i<n;i++)vis[i]=false;
int c=0;
for(int i=0;i<n;i++){
int v=i;
while(!vis[v]){
vis[v]=true;
if(vis[t[v]])break;
p[c]=v;
q[c]=t[v];
c++;
v=t[v];
}
}
for(int i=0;i<n;i++)t[i]=s[i],a[s[i]]=i;
for(int i=0;i<c;i++){
swap(t[x[i]],t[y[i]]);
a[t[x[i]]]=x[i];
a[t[y[i]]]=y[i];
p[i]=a[p[i]];
q[i]=a[q[i]];
swap(t[p[i]],t[q[i]]);
a[t[p[i]]]=p[i];
a[t[q[i]]]=q[i];
}
for(int i=c;i<r;i++)p[i]=0,q[i]=0;
return r;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
3 ms |
632 KB |
Output is correct |
| 22 |
Correct |
3 ms |
604 KB |
Output is correct |
| 23 |
Correct |
3 ms |
632 KB |
Output is correct |
| 24 |
Correct |
3 ms |
632 KB |
Output is correct |
| 25 |
Correct |
3 ms |
632 KB |
Output is correct |
| 26 |
Correct |
3 ms |
632 KB |
Output is correct |
| 27 |
Correct |
3 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
504 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
508 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
3 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
504 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
508 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
184 ms |
15208 KB |
Output is correct |
| 16 |
Correct |
191 ms |
23544 KB |
Output is correct |
| 17 |
Correct |
226 ms |
24692 KB |
Output is correct |
| 18 |
Correct |
68 ms |
20060 KB |
Output is correct |
| 19 |
Correct |
156 ms |
23260 KB |
Output is correct |
| 20 |
Correct |
180 ms |
23932 KB |
Output is correct |
| 21 |
Correct |
179 ms |
23964 KB |
Output is correct |
| 22 |
Correct |
179 ms |
20244 KB |
Output is correct |
| 23 |
Correct |
196 ms |
25580 KB |
Output is correct |
| 24 |
Correct |
226 ms |
25160 KB |
Output is correct |
| 25 |
Correct |
226 ms |
24976 KB |
Output is correct |
| 26 |
Correct |
177 ms |
23988 KB |
Output is correct |
| 27 |
Correct |
160 ms |
23180 KB |
Output is correct |
| 28 |
Correct |
217 ms |
25156 KB |
Output is correct |
| 29 |
Correct |
211 ms |
24512 KB |
Output is correct |
| 30 |
Correct |
109 ms |
22552 KB |
Output is correct |
| 31 |
Correct |
212 ms |
25072 KB |
Output is correct |
| 32 |
Correct |
199 ms |
24636 KB |
Output is correct |
| 33 |
Correct |
226 ms |
25248 KB |
Output is correct |
| 34 |
Correct |
212 ms |
25180 KB |
Output is correct |
| 35 |
Correct |
162 ms |
22836 KB |
Output is correct |
| 36 |
Correct |
58 ms |
21500 KB |
Output is correct |
| 37 |
Correct |
230 ms |
25392 KB |
Output is correct |
| 38 |
Correct |
215 ms |
24892 KB |
Output is correct |
| 39 |
Correct |
210 ms |
24440 KB |
Output is correct |
