# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
787717 |
2023-07-19T11:37:32 Z |
vnm06 |
Sorting (IOI15_sorting) |
C++14 |
|
116 ms |
22664 KB |
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
int b[200005];
int prebroj()
{
int ans=n;
for(int i=0; i<n; i++)
{
if(!b[i]) continue;
ans--;
int t=b[i]-1;
b[i]=0;
while(b[t]!=0)
{
int t2=b[t];
b[t]=0;
t=t2-1;
}
}
return ans;
}
int sp[2][200005], brsp=0;
int pos[200005];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n=N;
for(int i=0; i<n; i++) a[i]=S[i]+1;
int le=-1, ri=M;
while(ri-le>1)
{
int mid=(le+ri)/2;
for(int i=0; i<n; i++) b[i]=a[i];
for(int j=0; j<mid; j++) swap(b[X[j]], b[Y[j]]);
if(prebroj()<=mid) ri=mid;
else le=mid;
}
for(int i=0; i<n; i++) b[i]=a[i];
for(int j=0; j<ri; j++) swap(b[X[j]], b[Y[j]]);
for(int i=0; i<n; i++) pos[b[i]]=i;
for(int i=0; i<n; i++)
{
if(b[i]==i+1) continue;
sp[0][brsp]=b[i];
sp[1][brsp]=i+1;
brsp++;
int tp=pos[i+1];
pos[b[i]]=pos[i+1];
pos[i+1]=i;
swap(b[i], b[tp]);
}
for(int i=0; i<n; i++) pos[a[i]]=i;
for(int i=0; i<brsp; i++)
{
swap(a[X[i]], a[Y[i]]);
swap(pos[a[X[i]]], pos[a[Y[i]]]);
P[i]=pos[sp[0][i]];
Q[i]=pos[sp[1][i]];
swap(pos[sp[0][i]], pos[sp[1][i]]);
swap(a[pos[sp[0][i]]], a[pos[sp[1][i]]]);
}
for(int i=brsp; i<ri; i++) P[i]=Q[i]=0;
return ri;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
324 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 |
0 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 |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
580 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 |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
452 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
448 KB |
Output is correct |
9 |
Correct |
1 ms |
448 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
452 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
448 KB |
Output is correct |
9 |
Correct |
1 ms |
448 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
93 ms |
19972 KB |
Output is correct |
16 |
Correct |
99 ms |
20412 KB |
Output is correct |
17 |
Correct |
109 ms |
21484 KB |
Output is correct |
18 |
Correct |
48 ms |
15568 KB |
Output is correct |
19 |
Correct |
94 ms |
19216 KB |
Output is correct |
20 |
Correct |
99 ms |
19836 KB |
Output is correct |
21 |
Correct |
98 ms |
19824 KB |
Output is correct |
22 |
Correct |
89 ms |
16900 KB |
Output is correct |
23 |
Correct |
107 ms |
22364 KB |
Output is correct |
24 |
Correct |
110 ms |
22056 KB |
Output is correct |
25 |
Correct |
109 ms |
21736 KB |
Output is correct |
26 |
Correct |
98 ms |
19788 KB |
Output is correct |
27 |
Correct |
87 ms |
19092 KB |
Output is correct |
28 |
Correct |
110 ms |
21916 KB |
Output is correct |
29 |
Correct |
106 ms |
21076 KB |
Output is correct |
30 |
Correct |
73 ms |
18124 KB |
Output is correct |
31 |
Correct |
107 ms |
21512 KB |
Output is correct |
32 |
Correct |
109 ms |
21644 KB |
Output is correct |
33 |
Correct |
111 ms |
22020 KB |
Output is correct |
34 |
Correct |
107 ms |
21916 KB |
Output is correct |
35 |
Correct |
92 ms |
18972 KB |
Output is correct |
36 |
Correct |
39 ms |
16720 KB |
Output is correct |
37 |
Correct |
116 ms |
22664 KB |
Output is correct |
38 |
Correct |
111 ms |
21720 KB |
Output is correct |
39 |
Correct |
109 ms |
21896 KB |
Output is correct |