#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

const int S = 5e7 + 11;
const int N = 2e6 + 11;
bool p[S], k[N];
int v[S];

vector<int> solve(vector<int> A) {

    int s = 0;
    for(int ch : A) {
        s += ch;
    }
    p[0] = p[s] = true;
    v[s] = 0;
    for(int i = 0; i <= A.size() - 1; i++) {
        for(int j = s - 1; j >= A[i]; j--) {
            if(p[j]) continue;
            if(p[j - A[i]]) {
                p[j] = true;
                v[j] = i;
            }
        }
    }
    int i;
    for(i = s / 2 + s % 2; i <= s; i++) {
        if(p[i]) break;
    }
    vector<int> ans;
    while(i != 0) {
        ans.push_back(v[i]);
        k[v[i]] = true;
        i -= A[v[i]];
    }
    for(int i = 0; i < A.size(); i++) {
        if(!k[i]) ans.push_back(i);
    }
    return ans;
}
