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=301010;
const int B=20;
bool good[G][22];

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=0; i<=min(20, n-B); ++i){
    for (int j=0; j<G; ++j){
      if (good[j][i]){
        int nv=p[n-1-i].first+j;
        if (nv<G) good[nv][i+1]=1;
      }
    }
  }
  for (int i=0; i<G; ++i){
    for (int j=0; j<=20; ++j){
      if (good[i][j]) good[i][j+1]=1;
    }
  }
  int b=min(n, B);
  int bt=1<<b;
  
  long long sa;
  long long sb;
  for (int i=0; i<bt; ++i){
    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;
        int gi=n-j-1;
        if (gi>20) gi=20;
        bool j1=0;
        if (0<=p1 && p1<G && good[p1][gi]){
          j1=1;
        }else if (0<=p2 && p2<G && good[p2][gi]){
          j1=0;
        }else if (0<=cp1 && cp1<G && good[cp1][gi]){
          j1=0;
        }else if (0<=cp2 && cp2<G && good[cp2][gi]){
          j1=1;
        }else{
          if (sa<sb) 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;
    }
    if (paras==0) break;
  }
  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