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

using namespace std;

typedef long long ll;

vector<int> vecglob;

bool comp(int a, int b)
{
    return vecglob[a] < vecglob[b];
}

vector<int> solve(std::vector<int> vec)
{
    vecglob = vec;
    vector<int> res;
    ll amount = (ll)vec.size();
    if(amount == 1) return {0};
    if(amount == 2) return {1, 0};
    ll best = LLONG_MAX, bestmask, tots = 0;
    bool powers = true;
    for(ll num : vec)
    {
        tots += num;
    }
    for(ll mask = 0; mask <= (1ll << (amount))-1; mask++)
    {
        ll s = 0, am = 0, big = 0;
        for(ll i = 0; i < amount; i++)
        {
            if(mask & (1ll << i))
            {
                am++;
                s += vec[i];
                big = max(big, (ll)vec[i]);
            }
        }
        if(s-big >= (tots+1)/2) continue;
        if(s < (tots+1)/2) continue;
        if(abs(am - amount - am) < best)
        {
            best = abs(am - amount - am);
            bestmask = mask;
        }
    }
    for(ll i = 0; i < amount; i++)
    {
        if(bestmask & (1ll << i)) res.push_back(i);
    }
    sort(res.begin(), res.end(), comp);
    for(ll i = 0; i < amount; i++)
    {
        if(!(bestmask & (1ll << i))) res.push_back(i);
    }
    return res;
}
