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

using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

#define sz(a)  (int)(a).size()
#define all(a) (a).begin(), (a).end()

vector<int> solve(vector<int> a) {
    int n = sz(a);
    ll S = accumulate(all(a), 0LL);
    
    pii p[n];
    for (int i = 0; i < n; i++) {
        p[i] = {a[i], i};
    }
    sort(p, p + n);

    vector<int> ans;
    int mn = INT_MAX;
    for (int mk = 0; mk < 1 << n; mk++) {
        ll sm = 0;
        int cnt = 0;
        for (int i = 0; i < n && sm < S / 2.0; i++) {
            if (mk >> i & 1) {
                cnt++;
                sm += p[i].ff;
            }
        }

        if (cnt == __builtin_popcount(mk) && !(sm < S / 2.0) && abs(cnt - (n - cnt)) < mn) {
            mn = abs(cnt - (n - cnt));
            
            ans.clear();
            for (int i = 0; i < n; i++) {
                if (mk >> i & 1) ans.push_back(p[i].ss);
            }
            for (int i = 0; i < n; i++) {
                if (!(mk >> i & 1)) ans.push_back(p[i].ss);
            }
        }
    }

    // cout << "mn " << mn << ' ' << S << endl;
    // int sm = 0;
    // for (auto i : ans) {
    //     cout << a[i] << ' ' << (sm += a[i]) << endl;
    // }
    // cout << endl;

    return ans;
}