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

using namespace std;

const int MAXN = 20;

int perm[MAXN + 1];
int mini, n, i;
long long s, s2;
vector<int> a;
int f[MAXN + 1];
int v[MAXN + 1];

/*void bkt( int k ) {
    int cateA, cateB, diff;
    long long sumA, sumB;
    if( k == n ) {
        i = sumA = sumB = cateA = cateB = 0;
        while( i < n && sumA < s2 )
            sumA += v[ind[i++]], cateA++;
        while( i < n )
            sumB += v[ind[i++]], cateB++;

        diff = abs( cateA - cateB );
        if( diff < mini ) {
            mini = diff;
            for( i = 0; i < n; i++ )
                perm[i] = ind[i];
        }
    } else {
        for( i = 0; i < n; i++ ) {
            if( !f[i] ) {
                f[i] = 1;
                ind[k] = i;
                bkt( k + 1 );
                f[i] = 0;
            }
        }
    }
}*/

void bkt( int k ) {
    int i;
    if( k == n ) {
        long long sumA;
        int cateA, cateB, diff;
        cateA = cateB = diff = 0;
        sumA = 0;
        i = 0;
        while( i < n && sumA < s2 ) {
            sumA += a[v[i]];
            cateA++;
            i++;
        }
        while( i < n ) {
            cateB++;
            i++;
        }
        diff = abs( cateA - cateB );
        if( diff < mini ) {
            mini = diff;
            for( i = 0; i < n; i++ )
                perm[i] = v[i];
        }
        //for( i = 0; i < n; i++ )
        //    cout << v[i] << ' ';
        //cout << '\n';
    } else {
        for( i = 0; i < n; i++ )
            if( !f[i] ) {
                f[i] = 1;
                v[k] = i;
                bkt( k + 1 );
                f[i] = 0;
            }
    }
}

std::vector<int> solve(std::vector<int> A) {
    //int i, n, diff, cateA, cateB, mini;
    //long long sumA, sumB, s, s2;
    a = A;
    n = a.size();
    s = 0;
    for( i = 0; i < n; i++ ) {
        s += a[i];
    }
    s2 = s / 2 + s % 2;
    mini = INT_MAX;
    bkt(0);
    //cout << '\n' << mini << '\n';
    vector<int> rez;
    for( i = 0; i < n; i++ )
        rez.push_back( perm[i] );
    return rez;
}
