#include "partition.h"
#include<algorithm>
#include<set>
#include<random>
using namespace std;

int S2 = 0;
int target;
bool check_perm(vector<int> &p, vector<int> &a) {
    int cnt = 0;
    int sum = 0;
    for(int i = 0; i < p.size() && sum < S2; i++) {
        cnt++;
        sum += a[p[i]];
    }

    return cnt == target;
}

std::vector<int> solve(std::vector<int> A) {
    vector<int> perm;
    S2 = 0;
    target = A.size() / 2 + A.size() % 2;

    for(int i = 0; i < A.size(); i++) {
        perm.push_back(i);
        S2 += A[i];
    }
    S2 += S2 % 2;
    S2 /= 2;

    mt19937 rng;
    while(!check_perm(perm, A)) {
        shuffle(perm.begin(), perm.end(), rng);
    }
    return perm;
}

