Omenat

#include <bits/stdc++.h>
typedef long long ll;
#define F first
#define S second

using namespace std;

const int M=50000;
int ans[101];
int curr[101];
pair<int,int> p[101];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  srand(time(0));
  int n;
  cin>>n;
  for (int i=0;i<n;i++) {
    int k;
    cin>>k;
    p[i]={k,i};
  }
  sort(p,p+n);
  reverse(p,p+n);
  int parsa=1e9;
  for (int r=0;r<M;r++) {
    
    int sum=0;
    for (int i=0;i<n;i++) {
      if (sum<0) {
	sum+=p[i].F;
	curr[p[i].S]=1;
      } else {
	sum-=p[i].F;
	curr[p[i].S]=2;
      }
    }
    if (abs(sum)<parsa) {
      parsa=abs(sum);
      for (int i=0;i<n;i++) ans[i]=curr[i];
    }
    random_shuffle(p,p+n);
  }
  for (int i=0;i<n;i++) cout<<ans[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