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;
 
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 main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	vector<pair<ll, int> > pp(n);
	for (int i=0;i<n;i++){
		cin>>p[i];
	}
	vector<int> v=solve1();
	ll val=eval(v);
	for (int t=0;t<100000;t++){
		vector<int> lol(n);
		for (int i=0;i<n;i++){
			lol[i]=rand()%2+1;
		}
		if (eval(lol)<val){
			v=lol;
		}
	}
	for (int i=0;i<n;i++){
		cout<<v[i]<<" ";
	}
}

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