#include <algorithm>
#include "partition.h"

#define INF 10000000

using namespace std;

vector<int> solve(vector<int> V) {
    vector<int> perm, rasp;
    int N = V.size(), S = 0;
    int sum, d, dmin, i;

    for (i = 0; i < N; i++) {
        perm.push_back(i);
        rasp.push_back(i);
        S += V[i];
    }

    dmin = INF;
    do {
        sum = i = 0;
        while (sum < (S + 1) / 2) {
            sum += V[perm[i++]];
        }
        d = abs(i - (N - i));

        if (d < dmin) {
            dmin = d;
            for (i = 0; i < N; i++) {
                rasp[i] = perm[i];
            }

            if (dmin == N % 2) {
                break;
            }
        }
    } while (next_permutation(perm.begin(), perm.end()));

    return rasp;
}
