-
Notifications
You must be signed in to change notification settings - Fork 1
/
Almost Sorted.cs
103 lines (88 loc) · 2.33 KB
/
Almost Sorted.cs
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AlmostSorted
{
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n];
string[] split = Console.ReadLine().Split(' ');
for (int i = 0; i < n; i++)
{
arr[i] = int.Parse(split[i]);
}
int s = 1;
while (s < n && arr[s] >= arr[s - 1])
{
s++;
}
if (s == n)
{
Console.WriteLine("yes");
return;
}
int e = n - 2;
while (e >= 0 && arr[e] <= arr[e + 1])
{
e--;
}
s--;
e++;
// Lets try swapping
int temp = arr[s];
arr[s] = arr[e];
arr[e] = temp;
if (s > 0 && arr[s] < arr[s - 1])
{
Console.WriteLine("no");
return;
}
if (e < n - 1 && arr[e] > arr[e + 1])
{
Console.WriteLine("no");
return;
}
// Is it assending from s to e?
bool isAscending = true;
for (int i = s + 1; i <= e; i++)
{
if (arr[i] < arr[i - 1])
{
isAscending = false;
break;
}
}
if (isAscending)
{
Console.WriteLine("yes");
Console.WriteLine("swap {0} {1}", s+1, e+1);
return;
}
// Lets try reverse
temp = arr[s];
arr[s] = arr[e];
arr[e] = temp;
isAscending = true;
for (int i = e - 1; i >= s; i--)
{
if (arr[i] < arr[i + 1])
{
isAscending = false;
break;
}
}
if (isAscending)
{
Console.WriteLine("yes");
Console.WriteLine("reverse {0} {1}", s + 1, e + 1);
return;
}
Console.WriteLine("no");
}
}
}