#include "partition.h"
#include <algorithm>
#include <cstdint>
using namespace std;

#define sortIfNot(range, comp) if (!ranges::is_sorted(range, comp)) { ranges::sort(range, comp); }

vector<int> solve(vector<int> A) {
	int64_t s = 0, s2 = 0;
	for (const int &i : A) s += i;
	vector<pair<int, int>> aclz[33], a;
	for (int i = 0; i < A.size(); i++) aclz[__builtin_clz(A[i])].emplace_back(A[i], i);
	a.reserve(A.size());
	for (int i = 32; i >= 0; i--) {
		sortIfNot(aclz[i], [](auto &x, auto &y) { return x.first < y.first; });
		for (auto &j : aclz[i]) a.emplace_back(j);
	}
	const int n = a.size() + 1 >> 1;
	for (int i = 0; i < n; i++) s2 += a[i].first;
	for (int i = n - 1; i >= 0 && s2 << 1 < s; i--) {
		s2 -= a[i].first;
		swap(a[i], a[i + a.size() - n]);
		s2 += a[i].first;
	}
	vector<int> res(a.size());
#pragma GCC ivdep
	for (int i = 0; i < a.size(); i++) res[i] = a[i].second;
	return res;
}