#include "partition.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

std::vector<int> perm;
std::vector<int> ans;

std::vector<int> solve(std::vector<int> A)
{
    ans.resize(A.size(), 0);
    perm.resize(A.size(), 0);
    std::iota(perm.begin(), perm.end(), 0);
    
    int total = 0;
    for(int i = 0 ; i < A.size() ; ++i)
    {
        total += A[i];
    }

    int best = 1e9;

    do
    {
        int sum = 0, split = 0;
        for(int i = 0 ; i < perm.size() ; ++i)
        {
            sum += A[perm[i]];

            if(sum >= total / 2)
            {
                split = i;
                break;
            }
        }

        int left = split + 1;
        int right = perm.size() - left;

        int current = left - right;
        if(std::abs(current) < best)
        {
            best = std::abs(current);
            ans = perm;
        }
    }
    while(std::next_permutation(perm.begin(), perm.end()));

    return ans;
}
