Omenat

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <random>
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;

ll dp[MN][MS];

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

bool cur[MN];

std::mt19937 rng(666);
double rnd() {
	return rng() / (double)rng.max();
}
ll better(ll a, ll b) {
	return llabs(a) < llabs(b) ? a : b;
}

int scount;
ll ssum;

void solveSmall(ll bsum) {
	if (llabs(bsum) > ssum) {
		for(int i=0; i<scount; ++i) {
			res[i] = bsum<0;
		}
		return;
	}
	int x=scount;
	int sum=bsum;
	while(x>0) {
		int v=vs[x-1];
		ll a = dp[x-1][sum+v + MS2];
//		ll b = dp[x-1][sum-v + MS2];
//		if (better(a,b) == a) {
		if (a == dp[x][sum + MS2]) {
			res[x-1] = 1;
			sum += v;
		} else {
			res[x-1] = 0;
			sum -= v;
		}
		--x;
	}
}

ll smallRes(ll bsum) {
	if (llabs(bsum) > ssum) {
		return llabs(bsum) - ssum;
	}
	return llabs(dp[scount][MS2+bsum]);
}

void sa() {
	ll r=0;
	for(int i=scount; i<n; ++i) {
		cur[i] = rng()&1;
		r += (2*cur[i]-1)*vs[i];
	}
	ll best = smallRes(r);
	memcpy(res, cur, sizeof(res));
	solveSmall(r);
	int iters=0;
	for(double t=20; t>0.001; t*=0.9999997) {
		++iters;
		int x = rng()%n;
		int sign = cur[x] ? -2 : 2;
		ll rr = r + sign * vs[x];
		ll srr = smallRes(rr);
//		if (srr < smallRes(r) || t>rnd()) {
		if (true) {
			cur[x] ^= 1;
			r = rr;
			if (srr < best) {
				best = srr;
				memcpy(res,cur,sizeof(res));
				solveSmall(rr);
			}
		}
	}
	cerr<<"iters "<<iters<<'\n';
	cerr<<"best "<<best<<'\n';
}

int main() {
	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;

	ll sum=0;
	for(int i=0; i<n; ++i) {
		sum+=vs[i];
		if (sum < MS2) {
			ssum = sum;
			scount = i+1;
		}
	}
	cerr<<"scount "<<scount<<'\n';
//	scount=ssum=0;

	for(int i=0; i<MS; ++i) {
		dp[0][i] = i-MS2;
	}
	for(int i=1; i<=scount; ++i) {
		int v = vs[i-1];
		for(int j=0; j<MS; ++j) {
			if (j>v && j+v<MS) {
				dp[i][j] = better(dp[i-1][j-v], dp[i-1][j+v]);
			} else {
				dp[i][j] = 1e15;
			}
//			if (llabs(dp[i][j]) < ssum) cout<<"dp "<<i<<' '<<j<<" = "<<dp[i][j]<<'\n';
		}
	}
//	cout<<dp[scount][MS2]<<'\n';

//	assert(sum<MS2);

	if (scount == n) {
		solveSmall(0);
	} else {
		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

scount 0
iters 33011621
best 72

Test 2

Verdict: ACCEPTED

scount 0
iters 33011621
best 218

Test 3

Verdict: ACCEPTED

scount 0
iters 33011621
best 410

Test 4

Verdict: ACCEPTED

scount 0
iters 33011621
best 20

Test 5

Verdict: ACCEPTED

scount 0
iters 33011621
best 42

Test 6

Verdict: ACCEPTED

scount 0
iters 33011621
best 508

Test 7

Verdict: ACCEPTED

scount 0
iters 33011621
best 992

Test 8

Verdict: ACCEPTED

scount 0
iters 33011621
best 264

Test 9

Verdict: ACCEPTED

scount 0
iters 33011621
best 34

Test 10

Verdict: ACCEPTED

scount 0
iters 33011621
best 298