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

std::vector<int> solve(std::vector<int> A) {
    std::vector<int> p(A.size());
    for (int i = 0; i < A.size(); i++) p[i] = i;
    std::sort(p.begin(), p.end(), [&A] (const auto a, const auto b) { return A[a] > A[b]; });
    std::vector<int> p1, p2;
    long long s1 = 0, s2 = 0;
    for (const auto i : p) {
        if (s1 <= s2) {
            p1.push_back(i);
            s1 += A[i];
        } else {
            p2.push_back(i);
            s2 += A[i];
        }
    }
    p1.insert(p1.end(), p2.begin(), p2.end());
    return p1;
}

/*
1 0 3 8 2 6 7 4 5
6 5 3 3 6 4 4 1 1

5 6 6 3 1 1 4 4 3
1 1 3 3 4 4 5 6 6
6 5 4 1 1 | 3 3 4 6

2 7 3 6 4 0 1 5
3 3 2 2 3 2 2 2

2 2 3 2 3 2 2 3
2 2 2 2 2 3 3 3
3 3 2 2 | 2 2 2 3
3 3 3 2 | 2 2 2 2
*/
