Omenat

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

int main() {
	clock_t c0 = clock();
	std::mt19937 gen;
	int n;
	std::cin >> n;
	std::vector<int> p(n);
	long e = 0;
	while (n) {
		--n;
		std::cin >> p[n];
		e += p[n];
	}
	std::vector<int> p0(p);
	long e0 = e;
	while (e0 != 0 && (clock() - c0) * 1.0 / CLOCKS_PER_SEC < 0.95) {
		for (int i = 0; i < 300000; ++i) {
			++n;
			int r = gen() % p.size();
			if (p[r] * e < 0) {
				continue;
			}
			p[r] = -p[r];
			e += p[r] * 2;
			if (std::abs(e) < std::abs(e0)) {
				e0 = e;
				p0 = p;
				if (e0 == 0) {
					break;
				}
			}
		}
	}
	for (int i: p0) {
		std::cout << (i < 0 ? "1 " : "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