Omenat

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

ll p[111];
int n;
const ll inf=1e18;

ll eval(vector<int>&a){
	ll v1=0;
	ll v2=0;
	for (int i=0;i<n;i++){
		if (a[i]==1){
			v1+=p[i];
		}
		else{
			v2+=p[i];
		}
	}
	return llabs(v1-v2);
}

vector<int> solve1(){
	vector<pair<ll, int> > pp(n);
	vector<int> r(n);
	for (int i=0;i<n;i++){
		pp[i]={p[i], i};
	}
	sort(pp.rbegin(), pp.rend());
	ll p1=0;
	ll p2=0;
	for (int i=0;i<n;i++){
		if (p1<p2){
			p1+=pp[i].F;
			r[pp[i].S]=1;
		}
		else{
			p2+=pp[i].F;
			r[pp[i].S]=2;
		}
	}
	return r;
}

int ps[111];
int ph[20][55];
int vv[111];

ll ss(int t){
	if (ps[t]==0) return 0;
	ll bv=inf;
	ll bvv=inf;
	int bb=0;
	for (int i=0;i<(1<<ps[t]);i++){
		ll v1=0;
		ll v2=0;
		for (int j=0;j<ps[t];j++){
			if (i&(1<<j)){
				v1+=p[ph[t][j]];
			}
			else{
				v2+=p[ph[t][j]];
			}
		}
		if (llabs(v1-v2)<bv){
			bv=llabs(v1-v2);
			bvv=v1-v2;
			bb=i;
		}
	}
	for (int j=0;j<ps[t];j++){
		if (bb&(1<<j)){
			vv[ph[t][j]]=1;
		}
		else{
			vv[ph[t][j]]=2;
		}
	}
	return bvv;
}

vector<int> solve2(int pk){
	for (int i=0;i<pk;i++){
		ps[i]=0;
	}
	vector<int> asd(n);
	for (int i=0;i<n;i++){
		asd[i]=i/pk;
	}
	random_shuffle(asd.begin(), asd.end());
	for (int i=0;i<n;i++){
		int tp=asd[i];
		ph[tp][ps[tp]++]=i;
	}
	vector<ll> lol;
	for (int i=0;i<pk;i++){
		lol.push_back(ss(i));
	}
	int bb=0;
	ll bv=inf;
	for (int i=0;i<(1<<pk);i++){
		ll v=0;
		for (int j=0;j<pk;j++){
			if (i&(1<<j)){
				v-=lol[j];
			}
			else{
				v+=lol[j];
			}
		}
		if (llabs(v)<bv){
			bv=llabs(v);
			bb=i;
		}
	}
	vector<int> r(n);
	for (int j=0;j<pk;j++){
		if (bb&(1<<j)){
			for (int t=0;t<ps[j];t++){
				vv[ph[j][t]]=3-vv[ph[j][t]];
			}
		}
	}
	for (int i=0;i<n;i++){
		r[i]=vv[i];
	}
	return r;
}

int main(){
	srand(time(0));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	clock_t t0=clock();
	vector<pair<ll, int> > pp(n);
	for (int i=0;i<n;i++){
		cin>>p[i];
	}
	vector<int> v=solve1();
	ll val=eval(v);
	while (1){
		vector<int> tv=solve2(20);
		if (eval(tv)<val){
			v=tv;
		}
		clock_t t1=clock();
		if (((double)(t1-t0)/CLOCKS_PER_SEC)>0.9) break;
	}
	for (int i=0;i<n;i++){
		cout<<v[i]<<" ";
	}
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED