#include "partition.h"

#include <iostream>
#include <vector>


#define X first
#define Y second
#define control std::cout<<"passed\n";
#define maxn 200005
#define maxlog 21
#define PB push_back

#pragma GCC optimize("Ofast" , "O3" , "unroll-loops")
#pragma GCC target("avx2")


typedef long long ll;
typedef std::pair <ll, ll> pll;


std::vector<int> solve(std::vector<int> a)
{
    ll sum = 0;
    for(auto& e : a)
        sum += e;

    int n = a.size();

    ll ans = 1e9;
    ll ret = 0;


    for(int mask = 0; mask < (1 << (n)); mask++)
    {
        ll sum1 = 0;
        for(int i = 0; i < n; i++)
            if(mask & (1 << i))
                sum1 += a[i];

        ll sum2 = sum - sum1;


        for(int i = 0; i < n; i++)
            if(mask & (1 << i))
                std::cerr << 1 << " ";
            else
                std::cerr << 0 << " ";
        std::cerr << "\n";
        std::cerr << sum1 << " " << sum2 << " " << __builtin_popcount(mask) << "\n";

        if(sum1 < sum2)
            continue;

        int diff = abs(n - __builtin_popcount(mask) * 2);
        std::cerr << "!! " << diff << "\n";
        if(ans > diff)
        {
            ans = diff;
            ret = mask;
        }
    }

    std::cerr << ans << "\n";
    std::cerr << ret << "\n";

    std::vector <int> rr;
    for(int i = 0; i < n; i++)
        if(ret & (1 << i))
            rr.PB(i);
    for(int i = 0; i < n; i++)
        if(!(ret & (1 << i)))
            rr.PB(i);
    return rr;
}
