#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
vector<int> solve(vector<int> a) {
    int n = a.size();
    long long difMi = n;
    int rasp;

    long long tot = 0;
    for(int i = 0; i < n; i++) tot += (long long)a[i];
    for(int msc = (1 << n) - 1; msc >= 0; msc--) {
        long long sum = 0;
        for(int j = 0; j < n; j++) {
            if(msc >> j & 1) sum += a[j];
        }

        if(sum * 2 >= tot) {
            int biti = __builtin_popcount(biti);
            long long dif = biti - (n - biti);
            dif = (0 > dif ? -dif : dif);
            if(difMi > dif) {
                difMi = dif;
                rasp = msc;
            }
        }
    }

    vector<int> perm;
    for(int i = 0; i < n; i++) {
        if(rasp >> i & 1) perm.push_back(i);
    }

    for(int i = 0; i < n; i++) {
        if(!(rasp >> i & 1)) perm.push_back(i);
    }

    if(false) {
        cout << "/>  " << tot << ": ";
        for(int poz : perm) cout << a[poz] << ' ';
        cout << '\n';
    }

    return perm;
}
