#include "partition.h"
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
using ll = long long;

const int MAX_N = 2e6;
int n;
ll total_sum, lim;
int a[MAX_N];
int min_dif;
bool taken[MAX_N];

std::vector<int> pos;
std::vector<int> sol;
void bkt(int idx, ll sum, int max_val) {
    if(idx >= n) {
        if(sum >= lim && sum - max_val < lim) {
            int sz = int(pos.size());
            if(abs(2 * sz - n) < min_dif) {
                min_dif = abs(2 * sz - n);
                sol = pos;
            }
        }
    } else {
        bkt(idx + 1, sum, max_val);
        pos.push_back(idx);
        bkt(idx + 1, sum + a[idx], std::max(max_val, a[idx]));
        pos.pop_back();
    }
}

std::vector<int> solve(std::vector<int> _a) {
    n = int(_a.size());
    for(int i = 0; i < n; i++) {
        a[i] = _a[i];
    }
    total_sum = 0;
    for(int i = 0; i < n; i++) {
        total_sum += a[i];
    }
    lim = (total_sum + 1) / 2;
    pos.clear();
    min_dif = 1e9;
    bkt(0, 0, 0);

    std::sort(sol.begin(), sol.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    for(int i = 0; i < n; i++) {
        taken[i] = false;
    }
    for(int x : sol) {
        taken[x] = true;
    }
    for(int i = 0; i < n; i++) {
        if(!taken[i]) {
            sol.push_back(i);
        }
    }
    
    return sol;
}
