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

using namespace std;

const int maxn = 25;
const int MAXPWR = 30;

int n;
int a[maxn];
bool bl[maxn];

vector<int> ans;
int ansDiff;

long long sum = 0;

void f(int idx)
{
    if (idx == n)
    {
        long long curr = 0, mx = 0, posMx = -1;
        int cnt0 = 0, cnt1 = 0;

        for (int i = 0; i < n; ++i)
        {
            if (bl[i] == 0)
            {
                if (mx < a[i])
                {
                    mx = a[i];
                    posMx = i;
                }
                ++cnt0;
                curr += a[i];
            }
            else
            {
                ++cnt1;
            }
        }

        if (cnt0 == 0) return;

        if (curr >= sum && curr - mx < sum && ansDiff > abs(cnt0 - cnt1))
        {
            ansDiff = abs(cnt0 - cnt1);
            ans.clear();

            for (int i = 0; i < n; ++i)
            {
                if (bl[i] == 0 && i != posMx) ans.push_back(i);
            }

            ans.push_back(posMx);

            for (int i = 0; i < n; ++i)
            {
                if (bl[i] == 1) ans.push_back(i);
            }
        }

        return;
    }

    for (int i = 0; i < 2; ++i)
    {
        bl[idx] = i;
        f(idx + 1);
    }
}

std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    sum = 0;

    if (n == 1) return {0};
    if (n == 2) return {1, 0};
    if (n == 3) return {0, 1, 2};

    for (int i = 0; i < n; ++i)
    {
        a[i] = A[i];
        bl[i] = false;
        sum += a[i];
    }

    if (sum % 2 == 0) sum /= 2;
    else sum = sum / 2 + 1;

    vector<int> v;
    for (int i = 0; i < n; ++i) v.push_back(i);

    ansDiff = n;
    ans.clear();

    do
    {
        long long curr = 0, cnt = 0;

        for (int i = 0; i < n; ++i)
        {
            curr += v[i];
            if (curr >= sum)
            {
                cnt = i + 1;
                break;
            }
        }

        if (ansDiff > abs(n - 2 * cnt))
        {
            ansDiff = abs(n - 2 * cnt);
            ans = v;
        }
    } while (next_permutation(v.begin(), v.end()));

    return ans;
}
