Omenat

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#define ll long long
#define N (2<<16)

using namespace std;

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#define ll long long
#define N (2<<16)

using namespace std;

int main () {
	int n;
	cin>>n;
	int v[n];
	ll s = 0;
	for (int i = 0; i < n; i++) {
		cin>>v[i];
		s += (long long)v[i];
	}
	while (s / 2 > 2500000) {
		for (int i = 0; i < n; i++) {
			v[i] /= 10;
		}
		s /= 10;
	}
	s /= 2;
	int x[s + 1];
	for (int i = 0; i < s + 1; i++) x[i] = 0;
	x[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int z = s; z >= v[i]; z--) {
			if (x[z]) continue;
			if (x[z - v[i]]) x[z] = i + 1;
		}
	}
	bool b[n];
	//for (int i : x) cout<<i<<" ";
	//cout<<endl;
	for (int i = 0; i < n; i++) b[i] = false;
	for (int i = s; i >= 0; i--) {
		if (x[i]) {
			while (i != 0) {
				//cout<<x[i] - 1<<endl;
				b[x[i] - 1] = true;
				i -= v[x[i] - 1];
			}
			break;
		}
	}
	for (bool r : b) {
		cout<<(2 - (int)r)<<" ";
	}
	cout<<endl;
}

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