#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
long long bits[50],v[50];
vector<int>rez;
std::vector<int> solve(std::vector<int> A)
{
    for(int i=0;i<50;i++)
    {
        bits[i]=0;
        v[i]=0;
    }
    rez.clear();
    long long n=A.size(),sum=0,minn;
    minn=n;
    for(long long i=0; i<n; i++)
        sum+=A[i];
    for(long long i=0; i<pow(2,n); i++)
    {
        long long cnt=0,ci=i;
        for(long long j=0; j<n; j++)
        {
            bits[j]=0;
            bits[j]=ci%2;
            v[j]=0;
            ci/=2;
        }
        for(long long j=0; j<n; j++)
        {
            if(bits[j]==1)
            {
                v[cnt]=j;
                cnt++;
            }
        }
        sort(v,v+cnt);
        long long s1=0,s2=0;
        for(long long j=0; j<cnt-1; j++)
            s1+=A[v[j]];
        s2=s1+A[v[cnt-1]];
        if(2*s1<sum&&2*s2>=sum)
        {
            long long l1=cnt,l2;
            l2=n-l1;
            if(minn>abs(l1-l2))
            {
                rez.clear();
                for(long long j=0; j<cnt; j++)
                    rez.push_back(v[j]);
                for(long long j=0; j<n; j++)
                {
                    if(bits[j]==0)
                        rez.push_back(j);
                }
                minn=abs(l1-l2);
            }
            if(minn==n%2)
                return rez;
        }
    }
    return rez;
}

