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

using namespace std;
const int MAXN = 2e6;

vector<int> rez;
vector<int> v;
int comb[MAXN + 1]; //daca iau indicele i sau nu
int mini, n;
long long s2;

void bkt( int k ) {
    long long sumA;
    int i, cntA, cntB, diff, flag;
    if( k == n ) {
        sumA = 0;
        cntA = cntB = diff = flag = 0;
        //vector<int> ind;
        for( i = 0; i < n; i++ )
            if( comb[i] == 1 ) { //prima jumatate
                cntA++;
                sumA += v[i];
                if( sumA >= s2 )
                    flag++;
                //ind.push_back( i );
            } else {
                cntB++;
            }
        diff = abs( cntA - cntB );
        if( flag == 1 && diff < mini ) {
            //for( i = 0; i < n; i++ )
            //    if( comb[i] == 0 )
            //        ind.push_back( i );
            mini = diff;
            for( i = 0; i < n; i++ )
                rez[i] = comb[i];
            //rez = ind;
        }
    } else {
        for( i = 1; i >= 0; i-- ) {
            comb[k] = i;
            bkt( k + 1 );
        }
    }
}

std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    v = A;
    long long s;

    s = 0;
    for( int i = 0; i < n; i++ ) {
        s += v[i];
    }

    s2 = s / 2 + s % 2;
    mini = INT_MAX;
    rez.resize( n );
    bkt( 0 );
    //cout << mini << '\n';
    vector<int> ans;
    for( int i = 0; i < n; i++ )
        if( rez[i] == 1 )
            ans.push_back( i );

    for( int i = 0; i < n; i++ )
        if( rez[i] == 0 )
            ans.push_back( i );
    return ans;
}
