PROBLEM LINK:
PRACTICE
Editorialist: Aditya Verma
DIFFICULTY:
HARD
PREREQUISITES:
Sorting, Set
PROBLEM:
Virat Kohli loves integer sequences very much. He especially likes stairs(he barely uses lifts). Sequence a1, a2, …, an is stairs if there is such index i (1 ≤ i ≤ n), that the following condition is met: a1 < a2 < … < ai - 1 < ai > ai + 1 > … > a|a| - 1 > a|a|.
For example, sequences [1, 2, 3, 2] and [4, 2] are stairs and sequence [3, 1, 2] isn’t.
Kohli spending his quarantine so he not filled bored so he given a task to his best friend ABD to utilize some time, but ABD wants your help so do it guys. Ee sala cup namde.
You have given a number n and you have to make a stair sequence. A stair sequence is a sequence in which either numbers (first strictly increase and then decrease) or (numbers should strictly decrease).
EXPLANATION:
In this problem we are given with some numbers. We need to arrange the maximum possible numbers from total numbers in a stair sequence.
We will be generating the resultant sequence from two parts of the sequence i.e. we will be first creating the first part of sequence and then second part of sequence, after that we will simply join both the sequences to make resultant.
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int num[n+1];
for(int i=0;i<n;i++){
cin >> num[i];
}
sort(num,num+n);
int largest = num[n-1];
set<int> first,second;
second.insert(largest);
for(int i=n-2;i >= 0;i--){
if(num[i] != largest){
if(num[i+1] == num[i]){
first.insert(num[i]);
}
else
second.insert(num[i]);
}
}
vector<int> ans;
for(auto it = first.begin();it != first.end();it++){
ans.push_back(*it);
}
for(auto it = prev(second.end());it != second.begin();it--){
ans.push_back(*it);
}
auto it = second.begin();
ans.push_back(*it);
for(auto it = ans.begin();it != ans.end();it++){
cout << *it <<" ";
}
}