#include "partition.h"
#include <vector>
#include <iostream>

int rez[2000001];
int vc[2000001];
int v[2000001];
int cnt[2000001];
int n;

void verificare (int& mini , int total)
{
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 1; i <= n; i++)
    {
        sum1 += v[cnt[i]];
        sum2++;
        if (sum1 >= total / 2)
        {
            break;
        }
    }
    if (max(sum2 , n - sum2) - min(sum2 , n - sum2) < mini)
    {
        mini = max(sum2 , n - sum2) - min(sum2 , n - sum2);
        for (int i = 1; i <= n; i++)
        {
            rez[i] = cnt[i];
        }
    }
}

void bkt (int k , int& mini , int total)
{
    if (k == n + 1)
    {
        verificare(mini , total);
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            if (vc[i] == 0)
            {
                vc[i] = 1;
                cnt[k] = i;
                bkt(k + 1 , mini , total);
                vc[i] = 0;
            }
        }
    }
}

std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    int total = 0;
    for (int i = 0; i <= n; i++)
    {
        total += A[i];
        v[i + 1] = A[i];
    }
    int mini = 10000000;
    bkt(1 , mini , total);
    std::vector<int> rezz;
    for (int i = 1; i <= n; i++)
    {
        rezz.push_back(rez[i] - 1);
    }
    return rezz;

}