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

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

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

void bkt (int k , long long& mini , long long 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();
    long long total = 0;
    int p = 0;
    int subtask2 = 0;
    for (int i = 0; i < n; i++)
    {
        total += A[i];
        v[i + 1] = A[i];
        if (A[i] == p)
        {
            subtask2++;
        }
        p *= 2;
    }
    if (subtask2 <= n)
    {
        int nr;
        if (n % 2 == 0)
        {
            nr = n / 2 - 1;
        }
        else
        {
            nr = n / 2;
        }
        std::vector<int> rezz;
        for (int i = 1; i <= nr; i++)
        {
            rezz.push_back(i - 1);
        }
        rezz.push_back(n - 1);
        for (int i = nr + 1; i < n; i++)
        {
            rezz.push_back(i - 1);
        }
        return rezz;
    }
    else
    {
        long long mini = 1e18;
        bkt(1 , mini , total);
        std::vector<int> rezz;
        for (int i = 1; i <= n; i++)
        {
            rezz.push_back(rez[i] - 1);
        }
        for (int i = 1; i <= n; i++)
        {
            vc[i] = 0;
        }
        return rezz;
    }

}