-
Notifications
You must be signed in to change notification settings - Fork 0
/
Almost Sorted
73 lines (72 loc) · 1.01 KB
/
Almost Sorted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int main(){
int n,m,i,j,x;
s1(n);
VLL arr(n+1);
VLL srr(n+1);
bool sorted = true;
cin>>arr[1];
For1(i,2,n+1){
cin>>arr[i];
if(arr[i]<arr[i-1])
sorted = false;
}
srr = arr;
srr[0] = -1;
SortV(srr);
//pfArr(srr);
if(sorted){
pfs("yes");
}else{
int l = -1,r = -1;
For1(i,1,n+1){
if(arr[i]!=srr[i]){
l = i;
break;
}
}
For1e1r(i,n,0){
if(arr[i]!=srr[i]){
r = i;
break;
}
}
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
sorted = true;
For1(i,1,n){
if(arr[i]>arr[i+1]){
sorted = false;
break;
}
}
if(sorted){
pfs("yes\nswap ");
pf(l);
pfs(" ");
pf(r);
}else{
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//pf(l);pf(r);
reverse(arr.begin()+l,arr.begin()+r+1);
//pfArr(arr);
//pfs("\n");
sorted = true;
For1(i,1,n){
if(arr[i]>arr[i+1]){
sorted = false;
break;
}
}
if(sorted){
pfs("yes\nreverse ");
pf(l);pfs(" ");pf(r);
}else{
pfs("no");
}
}
}
return 0;
}