Omenat

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <time.h>

int main() {
	clock_t c0 = clock();
	std::mt19937 gen;
	int n;
	std::cin >> n;
	std::vector<int> p(n), a(n), a0, b;
	a.reserve(n);
	b.reserve(n);
	a0.reserve(n);
	long e = 0;
	for (int i = 0; i < n; ++i) {
		std::cin >> p[i];
		a[i] = p[i];
		e += p[i];
	}
	e /= 2;
	a0 = a;
	long e0 = e;
	while (e0 != 0 && (clock() - c0) * 1.0 / CLOCKS_PER_SEC < 0.95) {
		for (int i = 0; i < 300000; ++i) {
			if (e > 0) {
				std::swap(a[gen() % a.size()], *a.rbegin());
				e -= *a.rbegin();
				b.push_back(*a.rbegin());
				a.pop_back();
				if (e <= 0 && -e < e0) {
					e0 = -e;
					a0 = a;
					if (e0 == 0) {
						goto done;
					}
				}
			} else {
				std::swap(b[gen() % b.size()], *b.rbegin());
				e += *b.rbegin();
				a.push_back(*b.rbegin());
				b.pop_back();
				if (e >= 0 && e < e0) {
					e0 = e;
					a0 = a;
					if (e0 == 0) {
						goto done;
					}
				}
			}
		}
	}
	done:
	for (int i: p) {
		auto j = std::find(a0.begin(), a0.end(), i);
		if (j != a0.end()) {
			a0.erase(j);
			std::cout << "1 ";
		} else {
			std::cout << "2 ";
		}
	}
	std::cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED