Omenat

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>    
using namespace std;
int n;
 
 
vector<pair<int, int> > p;
 
bool srt(pair<int, int> a, pair<int, int> b){ return a.first>b.first;}
 
 
int jako[101];
int tulos[101];
long long paras;
 
const int G=1010101;
const int B=14;
int good[G];
 
int main(){
  srand (time(NULL));
  
  long long paras=100000000000000ll;
  cin >> n;
  long long s=0;
  for (int i=0; i<n; ++i){
    int x;
    cin >> x;
    s+=x;
    p.push_back(make_pair(x, i));
  }sort(p.begin(), p.end(), srt);
  
  for (int i=min(20, n-B); i>=0; --i){
    for (int j=0; j<G; ++j){
      if (good[j]==1){
        int nv=p[i].first+j;
        if (nv<G) good[nv]=2;
      }
    }
    for (int j=0; j<G; ++j){
      if (good[j]==2)good[j]=1;
    }
  }
  
  int b=min(n, B);
  int bt=1<<b;
  
  long long sa;
  long long sb;
  for (int i=0; i<bt; ++i){
    for (int dd=0; dd<50; ++dd){
      sa=0; sb=0;
      for (int j=0; j<n; ++j){
        if (j<b){
          if (i&(1<<j)){
            sa+=p[j].first;
            jako[j]=1;
          }else{
            sb+=p[j].first;
            jako[j]=2;
          }
        }else{
          long long cp1=s/2-sa;
          long long cp2=s/2-sb;
          long long p1=s/2-sa-p[j].first;
          long long p2=s/2-sb-p[j].first;
          bool j1=0;
          if (0<=p1 && p1<G && good[p1]){
            j1=1;
          }else if (0<=p2 && p2<G && good[p2]){
            j1=0;
          }else if (0<=cp1&& cp1<G && good[cp1]){
            j1=1;
          }else if (0<=cp2 && cp2<G && good[cp2]){
            j1=0;
          }else{
            if (cp1<0) j1=0;
            else if (cp2<0) j1=1;
            else{
              int v=rand()%(cp1+cp2);
              if (v<cp1) j1=1;
              else j1=0;
            }
          }
          if (j1){
            sa+=p[j].first;
            jako[j]=1;
          }else{
            sb+=p[j].first;
            jako[j]=2;
          }
        }
      }
      long long d=sa-sb;
      if (d<0) d=-d;
      if (d<paras){
        for (int j=0; j<n; ++j){
          tulos[p[j].second]=jako[j];
        }
        paras=d;
      }
    }
  }
  for (int i=0; i<n; ++i) cout << tulos[i] << "\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