Algorithm/FindSecond.cpp at main · GyunHeee/Algorithm · GitHub

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
#include <iostream>
#include <vector>
#include <map>
using namespace std;

typedef map<int, vector<int>> map_t;

int tournament(int low, int high, vector<int>& S, map_t& M)
{
    if (low == high)
        return S[low];
    else {
        int mid = (low + high) / 2;
        int left = tournament(low, mid, S, M);
        int right = tournament(mid + 1, high, S, M);
        int winner = left, loser = right;
        if (winner < loser) swap(winner, loser);
        M.find(winner)->second.push_back(loser);
        return winner;
    }
}

int find_largest(int n, vector<int>& S, map_t&M)
{
    return tournament(1, n, S, M);
}

int main()
{
    int n, largest;
    cin >> n;
    vector<int> S(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> S[i];

    map_t loser_map;
    for (int i = 1; i <= n; i++)
        loser_map.insert(make_pair(S[i], vector<int>()));

    largest = find_largest(n, S, loser_map);
    for (int loser: loser_map.find(largest)->second)
        cout << loser << " ";
    cout << endl;
}