#include "partition.h"

#define ll long long

#include <bits/stdc++.h>

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    
    int n = A.size();
    ll sum_total = 0;
    for(int i = 0; i < n; i++) {
        sum_total += A[i];
    }

    if(n > 20) return A;

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

    vector<int> ans;

    int best = n, nr;
    ll sum_crt;
    do {
        sum_crt = 0;
        nr = 0;
        for(int i = 0; i < n && sum_crt < (sum_total + 1) / 2; i++) {
            sum_crt += A[perm[i]];
            nr++;
        }
        int crt = abs((n - nr) - nr);
        if(crt < best) {
            ans = perm;
            best = crt;
        }
        if(best == 0) {
            return ans;
        }
    } while(next_permutation(perm.begin(), perm.end()));
    return ans;
}
