#include "partition.h"
#include <algorithm>

using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();
    vector<int> idx(n);
    for(int i = 0; i < n; i++) {
        idx[i] = i;
    }
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return a[x] > a[y];
    });

    long long s1 = 0, s2 = 0;
    vector<int> idx1, idx2;
    idx1.reserve(n);
    idx2.reserve(n);
    for(int i = 0; i < n; i++) {
        if(s1 <= s2) {
            s1 += a[idx[i]];
            idx1.push_back(idx[i]);
        } else {
            s2 += a[idx[i]];
            idx2.push_back(idx[i]);
        }
    }

    if(s1 < s2) {
        swap(idx1, idx2);
    }

    vector<int> answer;
    answer.reserve(n);
    for(auto it : idx1) {
        answer.push_back(it);
    }
    for(auto it : idx2) {
        answer.push_back(it);
    }
    return answer;
}
