#include<bits/stdc++.h>
#include "partition.h"
using namespace std;


vector<int> solve(vector<int> a)
{
    vector<int>perm;
    int s=0,n = a.size();
    for(int i=0; i<n; i++)
    {
        s+=a[i];
        perm.push_back(i);
    }
    double trg = (double)(s)/(double)(2);
    int op,cnt,bb,sz1,sz2;
    int best = n + 1;
    for(int b = 0; b<(1<<n); b++)
    {
        op = cnt= 0;
        for(int i=0; i<n; i++)
        {
            if((bool)(b & (1<<i)) == 1)
            {
                op+=a[i];
                cnt++;
            }
        }
        sz1 = cnt+1;
        sz2 = n - (cnt+1);
        if(op > trg || abs(sz1-sz2) > best)
            continue;
        bb = -1;
        for(int i=0; i<n; i++)
        {
            if((bool)(b & (1<<i)) == 0)
            {
                if(op +a[i]>trg)
                {
                    bb = i;
                    break;
                }
            }
        }
        if(bb == -1)
            continue;
        best = abs(sz1-sz2);
        int id = 0;
        for(int i=0; i<n; i++)
        {
            if((bool)(b & (1<<i)) == 1)
                perm[id++] = i;
        }
        perm[id++] = bb;
        for(int i=0; i<n; i++)
        {
            if((bool)(b & (1<<i)) == 0 && i!=bb)
                perm[id++] = i;
        }
    }
    return perm;
}
