Omenat

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MN=101;
typedef long long ll;

typedef pair<int,int> P;
P ps[MN];
int vs[MN];

const int MS = 100*1000;
const int MS2 = MS/2;

bool dp[MN][MS];

bool res[MN];
bool rres[MN];
int n;

bool cur[MN];

double rnd() {
	return rand() / (double)RAND_MAX;
}

void sa() {
	ll r=0;
	for(int i=0; i<n; ++i) {
		cur[i] = rand()&1;
		r += (2*cur[i]-1)*vs[i];
	}
	ll best = r;
	memcpy(res, cur, sizeof(res));
	for(double t=10; t>0.01; t*=0.9999) {
		int x = rand()%n;
		int sign = cur[x] ? -2 : 2;
		ll rr = r + sign * vs[x];
		if (llabs(rr) < llabs(r) || t > rnd()) {
			cur[x] ^= 1;
			r = rr;
			if (llabs(r) < llabs(best)) {
				best = r;
				memcpy(res,cur,sizeof(res));
			}
		}
	}
}

int main() {
	srand(666);
	cin>>n;
	for(int i=0; i<n; ++i) {
		int x;
		cin>>x;
		ps[i]=P(x,i);
	}
	sort(ps,ps+n);
	for(int i=0; i<n; ++i) vs[i]=ps[i].first;

	int sum=0;
	for(int i=0; i<n; ++i) sum+=vs[i];

//	assert(sum<MS2);

	sa();

	for(int i=0; i<n; ++i) rres[ps[i].second] = res[i];
	for(int i=0; i<n; ++i) cout<<1+rres[i]<<' ';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