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

const int BITS = 10;
const int MASK = (1 << BITS) - 1;

const int masks[3] = {MASK, MASK << BITS, MASK << (2 * BITS)};

using ll = long long;

int n;
int fr[MASK + 1];
void radix(const std::vector<int> & A, std::vector<int> &ind) {
    std::vector<int> B(n);

    for (int iter = 0; iter < 3; iter++) {
        int M = masks[iter];
        const int sh_r = iter * BITS;

        for (int i = 0; i <= MASK; i++)
            fr[i] = 0;

        for (int i = 0; i < n; i++) {
            fr[(A[i] & M) >> sh_r]++;
        }

        for (int i = 1; i <= MASK; i++)
            fr[i] += fr[i - 1];

        for (int i = n - 1; i >= 0; i--) {
            B[--fr[(A[ind[i]] & M) >> sh_r]] = ind[i];
        }

        for (int i = 0; i < n; i++)
            ind[i] = B[i];

    }
}

std::vector<int> solve(std::vector<int> A) {
    n = A.size();

    ll sum_total = 0;
    std::vector<int> ind(n);

    for (int i = 0; i < n; i++) {
        sum_total += A[i];
        ind[i] = i;
    }

    radix(A, ind);

    ll sum_first_half = 0;
    for (int i = 0; i < (n + 1) / 2; i++)
        sum_first_half += A[ind[i]];

    int idx = 0;

    while (sum_first_half + sum_first_half < sum_total) {
        sum_first_half += A[ind[n - 1 - idx]] - A[ind[idx]];
        std::swap(ind[idx], ind[n - 1 - idx]);
        idx++;
    }

    std::vector<int> ans;
    ans.reserve(n);

    for (int i = idx; i < (n + 1) / 2; i++)
        ans.push_back(ind[i]);
    for (int i = idx - 1; i >= 0; i--)
        ans.push_back(ind[i]);
    for (int i = (n + 1) / 2; i < n; i++)
        ans.push_back(ind[i]);

    return ans;
}
