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

using namespace std;

vector<int> solve(vector<int> B)
{
    vector<pair<int,int>> A;
    vector<int> ans;
    long long i,cnt,masca,solutie,mini,y,s,suma,N;
    for(i=0;i<B.size();i++)
    {
        A.push_back({B[i],i});
    }
    sort(A.begin(),A.end());
    bool ok;
    N=A.size();
    solutie=(1LL<<N)-1;
    mini=N+1;
    suma=0;
    for(auto x:A)
        suma+=x.first;
    for(masca=0;masca<(1LL<<N);masca++)
    {
        cnt=__builtin_popcount(masca);
        if(abs(2*cnt-N)>=abs(2*mini-N))
            continue;
        s=y=0;
        ok=true;
        for(i=0;i<N;i++)
        {
            if(masca&(1LL<<i))
            {
                s+=A[i].first;
                y++;
            }
            if(2*s>=suma && y<cnt)
            {
                ok=false;
                break;
            }
        }
        if(2*s>=suma && ok==true)
        {
            solutie=masca;
            mini=cnt;
        }
    }
    //cerr<<solutie<<" "<<mini<<endl;
    for(i=0;i<N;i++)
    {
        if(solutie&(1LL<<i))
            ans.push_back(A[i].second);
    }
    for(i=0;i<N;i++)
    {
        if((solutie&(1LL<<i))==0)
            ans.push_back(A[i].second);
    }
    /*s=0;
    cerr<<"VERIF: ";
    for(i=0;i<ans.size();i++)
    {
        s+=A[ans[i]];
        cerr<<s<<" ";
    }
    cerr<<endl;*/
    return ans;
}
/*
3
4
1 2 4 8
9
5 6 6 3 1 1 4 4 3
8
2 2 3 2 3 2 2 3
*/
