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

using namespace std;

vector<int> ind;
vector<int> perm;

std::vector<int> solve(std::vector<int> v) {
    if( n <= 20 ) {
        int i, n, diff, cateA, cateB, mini;
        long long sumA, sumB, s, s2;
        n = v.size();
        s = 0;
        ind.clear();
        perm.clear();
        for( i = 0; i < n; i++ ) {
            ind.push_back( i );
            s += v[i];
        }
        s2 = ceil( (float)s / 2 );
        mini = INT_MAX;
        do {
            i = sumA = sumB = cateA = cateB = 0;
            while( i < n && sumA < s2 )
                sumA += v[ind[i++]], cateA++;
            while( i < n )
                sumB += v[ind[i++]], cateB++;

            diff = abs( cateA - cateB );
            if( diff < mini ) {
                mini = diff;
                perm = ind;
            }
        } while( next_permutation( ind.begin(), ind.end() ) && mini > 0 );
        //cout << '\n' << mini << '\n';
        return perm;
    } else
        return v;
}
