#include <bits/stdc++.h>
#include "partition.h"
#pragma GCC optimize("O3,Unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
const int MAXN = 2000000;///
const int INF = 2e9;
vector<int> vrez;
int v[MAXN], va[MAXN], vrez2[MAXN];
char cmp(int a, int b) {//pozitii
    return va[a] < va[b];
}
std::vector<int> solve(std::vector<int> A) {
    //resetez vectorii

    //pun mai intai cele mai mici (n + 1) / 2 - 1
    //si dupa prima parte e clar < s / 2
    int i, n, p, p2, j, minr, maxr, aux;
    long long sum, jum, s;
    n = A.size();
    sum = 0;
    minr = INF + 1;
    maxr = 0;
    for (i = 0; i < n; i++) {
        va[i] = A[i];
        v[i] = i;
        sum += va[i];
        if (va[i] < minr) {
            minr = va[i];
        }
        if (va[i] > maxr) {
            maxr = va[i];
        }
    }
    jum = (sum + 1) / 2;
    //daca impart in x, n - x sa fie s(x) < jum si s(x + 1) >= jum si s(x) este suma pe prefixul 0...i
    p = (n + 1) / 2;//primii p cei mai mici ii pun
    nth_element(v, v + p - 1, v + n, cmp);
    /*for (i = 0; i < n; i++) {
        printf("i = %d p = %d val = %d\n", i, p, v[i].val);
    }*/
    vrez.resize(n);
    if (n == 1) {
        vrez[0] = 0;
    } else if (n == 2) {
        //mai intai maximul ca sa fie dif = 0
        if (A[0] >= A[1]) {
            vrez[0] = 0;
            vrez[1] = 1;
        } else {
            vrez[0] = 1;
            vrez[1] = 0;
        }
    } else if (minr == maxr) {///
        for (i = 0; i < n; i++) {
            vrez[i] = i;
        }
    } else {
        //fara al p-lea sa aiba suma < jum si dupa cu el sa fie > jum
        s = 0;
        for (i = 0; i < n; i++) {
            if (i < p) {
                s += va[v[i]];
                vrez2[i] = v[p - i - 1];
            } else {
                vrez2[i] = v[i];
            }
        }
        aux = vrez2[0];
        vrez2[0] = vrez2[p - 1];
        vrez2[p - 1] = aux;
        //primele p - 1 au sigur suma < jum
        //il inlocuiesc pe ultimul cu maximul
        j = n - 1;
        p2 = p - 2;
        while (s < jum) {
            //pe pozitia p il pun pe maximul ramas j
            //si daca suma este < jum atunci dau swap la p cu p2
            s += va[vrez2[j]] - va[vrez2[p - 1]];//alea sunt pozitiile din vectorul original
            aux = vrez2[j];
            vrez2[j] = vrez2[p - 1];
            vrez2[p - 1] = aux;
            j--;
            if (j == p - 1) {
                j = n - 1;
            }
            if (s < jum) {
                aux = vrez2[p2];
                vrez2[p2] = vrez2[p - 1];
                vrez2[p - 1] = aux;
                p2--;
            }
        }
        for (i = 0; i < n; i++) {
            vrez[i] = vrez2[i];
        }
    }
    return vrez;
}
