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

using namespace std;

struct str {
    int val, idx;
};

bool comp(str a, str b) {
    return a.val < b.val;
}

void qsort(vector <str>P, int st, int dr) {
    int s, d, pivot;
    s = st;
    d = dr;
    pivot = P[(s + d) / 2].val;

    while (P[s].val < pivot) {
        s++;
    }
    while (P[d].val > pivot) {
        d--;
    }

    while (s < d) {
        swap(P[s], P[d]);

        do {
            s++;
        } while (P[s].val < pivot);
        do {
            d--;
        } while (P[d].val > pivot);
    }

    if (st < d) {
        qsort(P, st, d);
    }
    if (d + 1 < dr) {
        qsort(P, d + 1, dr);
    }
}

vector<int> solve(vector<int> V) {
    vector<int> p1, p2, rasp;
    vector<str> P;
    int N = V.size(), i;
    long long s1, s2;
    str aux;

    for (i = 0; i < N; i++) {
        aux.val = V[i];
        aux.idx = i;
        P.push_back(aux);
    }

    qsort(P, 0, N - 1);

    s1 = s2 = 0;
    for (i = 0; i < N; i++) {
        if (s1 <= s2) {
            s1 += P[i].val;
            p1.push_back(P[i].idx);
        } else {
            s2 += P[i].val;
            p2.push_back(P[i].idx);
        }
    }

    if (s1 > s2) {
        for (i = 0; i < p1.size(); i++) {
            rasp.push_back(p1[i]);
        }
        for (i = 0; i < p2.size(); i++) {
            rasp.push_back(p2[i]);
        }
    } else {
        for (i = 0; i < p2.size(); i++) {
            rasp.push_back(p2[i]);
        }
        for (i = 0; i < p1.size(); i++) {
            rasp.push_back(p1[i]);
        }
    }

    return rasp;
}
