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

using namespace std;
using ll = long long;

vector< pair<ll, int> > A;
ll S = 0;
int n;
vector<int> eu, sol;
int mini = 0;

void bkt(int it, ll suma){
    //cerr << "pot fi la " << it << " " << suma << '\n';
    if(suma * 2LL >= S){
        if( abs((int)eu.size() - (n - (int)eu.size())) < mini){
            mini = abs((int)eu.size() - (n - (int)eu.size()));
            sol = eu;
        }
        return;
    }
    if(it == n) return;

    bkt(it + 1, suma);

    eu.push_back(A[it].second);
    bkt(it + 1, suma + A[it].first);
    eu.pop_back();
}

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

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

    eu.clear(); sol.clear();
    A.resize(n);
    for(int i = 0; i < n; i++) A[i] = {a[i], i};
    sort(A.begin(), A.end());

    mini = n + 1;
    S = 0;
    for(int i = 0; i < n; i++) S += A[i].first;

    // 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

    bkt(0, 0);
    /*int check = 0;
    for(int i = 0; i < n; i++){
        check += a[ sol[i] ];
        if(check * 2 >= S){
            cout << "len = " << i + 1<< '\n';
            break;
        }
    }*/

    if(sol.size() != (n + 1) / 2 && sol.size() != n / 2){
        return {-1};
    }

    set<int> sunt;
    for(const auto &x : sol) sunt.insert(x);
    for(int i = 0; i < n; i++){
        if(sunt.find(i) == sunt.end()) sol.push_back(i);
    }

    return sol;
}
