“During the sorting, processing every element which is not yet at its final position is called a run. Which of the following cannot be the result after the second run of quicksort?” – This is a question in the Graduate Entrance Exam set. Now you are supposed to write a program to check the answers automatically.
Input Specification:
Each input file contains several test cases. The first line gives a positive integer $K$ ($\le 10$), which is the total number of cases. Then $K$ cases are given in the fomat
N
a[0] a[1] ... a[N-1]
where N
($3\le$N
$\le 10^5$) is the number of elements, and a[i]
‘s ($\le 10^9$) are distinct elements to be checked. All the numbers in a line are positive integers that are separated by spaces.
Output Specification:
For each test case, output in a line Yes
if it is possible to be the second run of quicksort, or No
if not.
Sample Input:
4
8
5 2 16 12 28 60 32 72
8
2 16 5 28 12 60 32 72
8
2 12 16 5 28 32 72 60
8
5 2 12 28 16 32 72 60
Sample Output:
Yes
Yes
Yes
No
Hint:
Case 1 is possible because we may choose 72 to be the pivot during the first run, and 28 to be the pivot during the second run.
Case 2 is possible because we may choose 2 to be the pivot during the first run, and 72 to be the pivot during the second run, or vice versa.
Case 3 is possible because we may choose 28 to be the pivot during the first run, 2 and 32 to be the pivots for the left- and right-hand side subsequences during the second run, respectively.
Case 4 is impossible because if we choose 12 to be the pivot during the first run, then the left-hand side subsequence would have no pivot; or if we choose 32 to be the pivot during the first run, then the right-hand side subsequence would have no pivot.
#include <iostream>
#include <vector>
using namespace std;
int vec[100010];
int lmax[100010];
int rmin[100010];
int lmax2[100010];
int rmin2[100010];
bool isFirstRun(int start, int end)
{
if (start >= end)
{
return true;
}
lmax2[start] = vec[start];
rmin2[end] = vec[end];
for (int i = start + 1; i <= end; i++)
{
lmax2[i] = max(vec[i], lmax2[i - 1]);
}
for (int i = end - 1; i >= start; i--)
{
rmin2[i] = min(vec[i], rmin2[i + 1]);
}
for (int i = start; i <= end; i++)
{
if (vec[i] >= lmax2[i] && vec[i] <= rmin2[i])
{
return true;
}
}
return false;
}
int main()
{
int k;
cin >> k;
while (k-- != 0)
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> vec[i];
}
bool ok = false;
lmax[0] = vec[0];
rmin[n - 1] = vec[n - 1];
for (int i = 1; i < n; i++)
{
lmax[i] = max(vec[i], lmax[i - 1]);
}
for (int i = n - 2; i >= 0; i--)
{
rmin[i] = min(vec[i], rmin[i + 1]);
}
for (int i = 0; i < n; i++)
{
if (vec[i] >= lmax[i] && vec[i] <= rmin[i])
{
if (isFirstRun(0, i - 1) && isFirstRun(i + 1, n - 1))
{
ok = true;
break;
}
}
}
if (ok)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}