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

using namespace std;

typedef int64_t ll;

std::vector<int> solve(std::vector<int> A) {
    ll S = accumulate(A.begin(), A.end(), 0LL);

    ll S2 = ceil(double(S) / 2);

    vector<int> v;

    vector<int> ans;

    ll n = A.size();
    ll diff1 = LLONG_MAX;
    ll BestSum = 0;
    for (ll i = 1; i <= (1 << n); ++i) {
        vector<int> cors;
        ll cnt1 = 0, sum1 = 0;
        for (ll j = 0; j < n; ++j) {
            if (sum1 >= S2) {
                break;
            }
            if (i & (1 << j)) {
                //cout << j << ' '; 
                cnt1++, sum1 += A[j];
                cors.push_back(j);
            }
        }

       // cout << endl;

        if (sum1 >= S2) {
            //for (ll x : cors) cout << x << ' ';
            //cout << endl;
            ll cnt2 = n - cnt1;
            ll cur_diff1 = abs(cnt2 - cnt1);


            if (cur_diff1 < diff1) {
                //cout << cur_diff1 << ' ' << diff1 << endl;
                diff1 = cur_diff1;
                ans = cors;
                BestSum = sum1;
            } 
        }
    }

    //for (ll x : ans) cout << x << ' ';

    //cout << endl;

    bool used[n] = {false};

    for (ll x : ans) {
        used[x] = true;
    }

    for (ll i = 0; i < n; ++i) {
        if (!used[i]) ans.push_back(i);
    }

    return ans;
}
/*
if (cur_diff1 < diff1) {
            diff1 = cur_diff1;
            ans = v;
            BestSum = sum1;
        } else if (cur_diff1 == diff1) {
            if (BestSum < sum1) {
                diff1 = cur_diff1;
                ans = v;
                BestSum = sum1;
            }
        }*/