Omenat

#include <iostream>
#include <vector>
#include <algorithm>
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;


int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  paras=100000000000000ll;
  
  cin >> n;
  p.resize(n);
  long long s=0;
  for (int i=0; i!=n; ++i){
    cin >> p[i].first;
    s+=p[i].first;
    p[i].second=i;
  }sort(p.begin(), p.end(), srt);
  s/=2;
  int b=min(n, 22);
  int bt=1<<b;
  ++b;
  
  long long sa;
  long long sb;
  int i, j;
  long long d;
  long long fbs=s+paras/2;
  for (i=0; i!=bt; ++i){
    sa=0; sb=0;
    for (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{
        if (sa<sb){
          sa+=p[j].first;
          jako[j]=1;
        }else{
          sb+=p[j].first;
          jako[j]=2;
        }
      }
      if (sa>fbs || sb>fbs) break;
    }
    d=sa-sb;
    if (d<0) d=-d;
    if (d<paras){
      for (j=0; j!=n; ++j) tulos[p[j].second]=jako[j];
      paras=d;
      fbs=s+paras/2;
    }
  }
  for (i=0; i!=n; ++i) cout << tulos[i] << "\n";
}

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