#include "partition.h"
#include <iostream>
using namespace std;
#include <map>
#include <queue>

std::vector<int> solve(std::vector<int> A) {
	vector<int> res;
	int n = A.size();
	vector<pair<int, int>>v;
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		v.push_back({ A[i], i });
		sum += A[i];
	}
	sort(v.begin(), v.end());
	vector<bool> used(n + 1, 0);
	int mn = n + 6;
	for (int mask = 0; mask < (1 << n); mask++) {
		long long s = 0;
		int c1 = 0;
		vector<bool> marked(n + 1, 0);
		bool fl = 0;
		for (int i = 0; i < n; i++) {
			if (mask & (1 << i)) {
				s += v[i].first;
				c1++;
				marked[v[i].second] = 1;
				if (s >= (sum + 1) / 2) {
					fl = 1;
					break;
				}
			}
		}
		if (abs(c1 - (n - c1)) < mn && s >= (sum + 1) / 2 && fl) {
			mn = c1 - (n - c1);
			used = marked;
		}
	}
	for (int i = 0; i < n; i++) {
		if (used[i]) res.push_back(i);
	}
	for (int i = 0; i < n; i++) {
		if (!used[i]) res.push_back(i);
	}
	return res;
}
