Rapunzel II

Now folks you have successfully passed all the missions. Now you have to fight the witch. To combat the witch you can’t fight alone. So you have some help. Along with Flynn Rider, there are soldiers fighting at your side. But as usual, the problem of leadership arose. Everyone wants a leader, but with a constraint. None of them wants their leader to be influential. Each soldier has a hitpoint , the soldier with hitpoints can be his leader if and only if and none of them wants to nominate themselves as the leader. So they can’t choose themselves as the leader. Every soldier wants his leader to be the strongest as possible. Can you help these soldiers as quickly as possible in order to save Rapunzel on time?

Input Format

The first line contains the number of test cases . Each test has two lines. The first line contains the total number of soldiers including Flynn, . The second line contains space-separated integers, each indicating the hitpoints of each player.

Constraints

for all

Output Format

For each test case output integers each indicating the hitpoints of the respective leaders. If a soldier couldn’t find a leader with the given requirement print -1 for him.

Sample Input 0

2
3
100 200 500
2
300 100

Sample Output 0

200 100 200
100 -1

Explanation 0

The first soldier can select a leader with hitpoints less than or equal to 200.
The second soldier can select a leader with hitpoints less than or equal to 400.
The third soldier can select a leader with hitpoints less than or equal to 1000.
In this case we can select both soldiers as mentors. Since every soldier wants their mentor to be the strongest as possible, he selects the one with 200 hitpoints.

Solution

By Suhas Dissanayake

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first < b.first;
}

int main() {
    int tests;
    cin >> tests;

    for(int t = 0; t < tests; t++){
        int n;
        cin >> n;

        vector<pair<int,int>> hps(n);
        for (int j = 0; j < n; ++j) {
            int k;
            cin >> k;
            hps[j] = {k, j};

        }

        vector<pair<int,int>> sortedhps = hps;

        sort(sortedhps.begin(), sortedhps.end(),cmp);

        for(pair<int,int> h: hps){
            int req = 2*h.first;
            int leader = -1;

            auto it = upper_bound(sortedhps.begin(), sortedhps.end(), make_pair(req,0), cmp);

            while (it != sortedhps.begin()) {
                --it;
                if (it->second != h.second) {
                    leader = it -> first;
                    break;
                }
            }

            cout << leader << " ";
        }
        cout << "\n";

    }

    return 0;
}