HackerEarth Shil and Survival Game problem solution

In this HackerEarth Shil and Survival Game problem solution, The Mad King arrested Shil's comrades for participating in a rebellion against the King. Instead of punishing them with death, the King decided to play the game of survival with them. The game is played as follows:

1. All the N people are forced to stand in a line.
2. Now the king randomly chooses any two persons standing next to each other in line and kills the one having lower strength.
3. King keeps on performing step 2 until there are only 2 survivors.
4. The last two survivors are forgiven for their crimes and are free to go.
5. As Shil is worried for his comrades, he wants to find out the ones who could survive - at least, one out of all the possible games.

Given N integers denoting the strengths of comrades, you must print the position of comrades who could survive at least one Game.

HackerEarth Shil and Survival Game problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 99991
#define inf 1e9

#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
//#define mp make_pair
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
#define gd(v) scanf("%d",&v)
#define pd(v) printf("%d\n",v)
#define gl(v) scanf("%lld",&v)
#define pl(v) printf("%lld\n",v)
#define fr freopen("input-10.txt","r",stdin)
#define fo freopen("output-10.txt","w",stdout)

int main(){
  int N;
  cin >> N;
  ll a[N];
  ll ma=0;
  ll idx;
  rep(i,N){
    cin >> a[i] ; ma=max(ma,a[i]) ;
    if( ma == a[i] ) idx=i;
  }
  vector<int>ans;
  ans.pb(idx);
  ma=0;
  rep(i,N){
    if(i==idx) break;
    ma=max(ma,a[i]);
    if(ma==a[i]){
      ans.pb(i);
    }
  }
  ma=0;
  for(int i=N-1;i>=0;i--){
    if(i==idx) break;
    ma=max(ma,a[i]);
    if(ma==a[i]){
      ans.pb(i);
    }
  }
  sort(ans.begin(),ans.end());
  for(auto x:ans){
    cout<<x+1<<" ";
  }
}

Second solution

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;
const int N = 100000;
const int V = 1000000000;

int a[N];
pii maxp[N + 1], maxs[N + 1];
int res[N];
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    assert(n >= 3); assert(n <= N);
    FOR(i, n)
    {
        cin >> a[i];
        assert(a[i] >= 1); assert(a[i] <= V);
    }
    maxp[1] = mp(a[0], 0);
    REP(i, 2, n)
    {
        if(a[i - 1] > maxp[i - 1].fi)
        {
            maxp[i] = mp(a[i - 1], i - 1);
        }
        else
        {
            maxp[i] = maxp[i - 1];
        }
    }
    maxs[1] = mp(a[n - 1], n - 1);
    REP(i, 2, n)
    {
        if(a[n - i] > maxs[i - 1].fi)
        {
            maxs[i] = mp(a[n - i], n - i);
        }
        else
        {
            maxs[i] = maxs[i - 1];
        }
    }
    REP(i, 1, n - 1)
    {
        int a = maxp[i].se;
        int b = maxs[n - i].se;
        res[a] = 1;
        res[b] = 1;
    }
    FOR(i, n)
    {
        if(res[i])
        {
            cout << i + 1 << " ";
        }
    }
    cout << endl;
    return 0;
}