#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> solve6sau2(vector<int> vec) {
    vector<int> ans(n);

    int minn = 500, sol = 0, special = 0, onessol = 0;
    long long sum = 0;

    for(int i : vec)
        sum = sum + 2 * i;

    int cct = 0;

    for(int mask = 0; mask < (1 << n); mask++) {
        cct++;

        if(cct != 5)
            continue;

        cct = 0;
        long long localsum = 0;
        int minim = 2e9, unu = 0, zero = n;

        for(int bit = 0; bit < n; bit++) {
            if((1 << bit)&mask) {
                unu++;
                zero--;

                localsum = localsum + 2 * vec[bit];
                minim = min(minim, vec[bit]);
            }
        }

        if(localsum >= sum / 2) {
            for(int bit = 0; bit < n; bit++) {
                if((1 << bit)&mask) {
                    if(localsum - vec[bit] < sum / 2) {
                        if(minn > abs(unu - zero)) {
                            minn = abs(unu - zero);
                            sol = mask;
                            special = bit;
                            onessol = unu;
                        }
                    }
                }
            }
        }
    }

    int poz = 0, last = n - 1;

    ans[onessol - 1] = special;

    for(int i = 0; i < n; i++) {
        if(i == special)
            continue;

        if((1 << i)&sol)
            ans[poz++] = i;
        else
            ans[last--] = i;
    }

    return ans;
}
std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    vector<int> ans(n);
    ans = solve6sau2(A);
    return ans;
}
