#include "partition.h"
#include <bits/stdc++.h>
#define MAXVAL 30000000
#define MAXN 2000
#define INF 1000000000

using namespace std;

int per[MAXN + 1], mini, per_min[MAXN + 1];

void bkt(int pos, int cur, int sum, vector <int> A){
    int i;
    if(cur >= sum / 2 +(sum % 2 == 1)){
        if(cur < mini){
            mini = cur;
            for(i = 0; i < A.size(); i++){
                per_min[i] = per[i];
            }
        }
    }else if(pos < A.size()){
        per[pos] = 1;
        bkt(pos + 1, cur + A[pos], sum, A);
        per[pos] = 0;
        bkt(pos + 1, cur, sum, A);
    }
}

vector<int> solve(vector<int> A){
    int N, i, sum;
    vector <int> rez, lft, rgt;

    N = A.size();
    sum = 0;
    for(i = 0; i < N; i++){
        sum += A[i];
    }

    for(i = 0; i < MAXN; i++){
        per[i] = per_min[i] = 0;
    }
    mini = INF;
    bkt(0, 0, sum, A);
    for(i = 0; i < N; i++){
        if(per_min[i] == 1){
            lft.push_back(i);
        }else{
            rgt.push_back(i);
        }
    }
    for(i = 0; i < lft.size(); i++){
        rez.push_back(lft[i]);
    }
    for(i = 0; i < rgt.size(); i++){
        rez.push_back(rgt[i]);
    }
//    for(i = 0; i < N; i++){
//        printf("%d ", A[rez[i]]);
//    }
//    printf("***\n");
    return rez;
}
//2
//4
//1 2 4 8
//5
//1 2 4 8 16
