#include "partition.h"
#include <vector>
#include <algorithm>
#pragma GCC optimize("unroll-loops","fast-maths")
#define mp make_pair

using namespace std;

vector<int> solve(vector<int> A)
{
    vector<pair<int,int>> v;

    int s = 0;
    int n = A.size();
    for(int i=0;i<n;i++)
        s+=A[i];
    for(int i=0;i<n;i++)
    {
        v.push_back(mp(A[i],i));
    }
    int minn = 1e9;
    vector<int> ans;
    do
    {
        int a = 0, b = 0;
        int curr = 0;
        for(auto it : v)
        {
            if(curr < s/2 + s%2)
                a++;
            else
                b++;
            curr+=it.first;
        }
        if(minn>abs(a-b))
        {
            minn=abs(a-b);
            ans.clear();
            for(auto it : v)
                ans.push_back(it.second);
        }
    }while(next_permutation(v.begin(),v.end()));
    return ans;
}

