#include<bits/stdc++.h>
#include "partition.h"

using namespace std;

vector<int> solve(vector<int> a){
    int n = a.size();

    if(n == 1) return {0};

    // osa pp ca solutia are fix (n+1)/2 elem
    // acuma trebe doar sa aleg acel subset de elemente a.i. sa dea suma finala > S/2
    // hai sa fac n <= 20

    vector< pair<int, int> > v;
    for(int i = 0; i < n; i++){
        v.push_back({a[i], i});
    }
    sort(v.begin(), v.end());
    set< pair<int, int> > pos;
    for(int i = (n + 1) / 2; i < n; i++) pos.insert(v[i]);

    int S = 0;
    for(int i = 0; i < n; i++) S += a[i];

    int suma = 0;
    for(int i = 0; i < (n + 1) / 2; i++) suma += v[i].first;

    int it = (n + 1) / 2 - 1;
    while(suma * 2 < S){
        // il replace pe cel de la it cu urm mai mare
        /*cerr << "v : ";
        for(int i = 0; i < (n + 1) / 2; i++) cerr << v[i].first << " ";
        cerr << '\n';
        cerr << "it = " << it << '\n';
        cerr << "pos : ";
        for(const auto &x : pos) cerr << x.first << " ";
        cerr << '\n';*/
        if(it < 0) break;
        auto i1 = pos.upper_bound({ v[it].first, -1 });
        if(i1 == pos.end()){
            it--; continue;
        }

        pos.insert(v[it]);
        suma -= v[it].first;
        v[it] = (*i1);
        suma += v[it].first;
        pos.erase(i1);
    }

    vector<int> sol;
    for(int i = 0; i < (n + 1) / 2; i++) sol.push_back(v[i].second);
    for(const auto &x : pos) sol.push_back(x.second);
    return sol;
}
