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

//#define DEBUG

#ifdef DEBUG
    #define D(x) cout << "    " << #x << " = " << x << endl;
    #define V(x) cout << "    " << #x << ": "; for(auto i : x) cout << i << ' '; cout << endl;
    #define N() cout << endl;
#else
    #define D(X)
    #define V(X)
    #define N()
#endif

vector<vector<int>> dp;

vector<int> solve(vector<int> A) {
    long long s = 0;

    for(int i : A)
    {
        s += i;
    }

    int lim = (s + 1) / 2;

    dp.push_back(vector<int>(1, -1));

    int idx = 0;

    for(long long i = 1;i <= lim;i++)
    {
        //D(i)
        dp.push_back(vector<int>());
        for(int id = 0;id < A.size(); id++)
        {
            int j = A[id]; 
            long long perv = i - j;
            if(perv < 0) continue;
            if(dp[perv].size() > 0 && dp[perv].back() < id)
            {
                dp[i] = dp[perv];
                dp[i].push_back(id);
                idx = i;
                break;
            }
        }


    }

    V(dp[idx]);

    vector<int> res;

    for(int i = 0;i < A.size();i++)
    {
        res.push_back(i);
    }

    int q = 0;
    for(int i = 1;i < dp[idx].size();i++)
    {
        D(res[dp[idx][i]])
        D(res[q])
        swap(res[dp[idx][i]], res[q]);
        q++;
    }

    return res;
}
