Omenat

// G
 
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef unsigned long long int ull;
 
mt19937 mt(0);
uniform_int_distribution<> flip(1, 2);
vector<pair<ull, int>> apples;
 
void print(const vector<char> &r) {
  for (char c : r)
    cout << c << '\n';
}
 
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ull a;
    cin >> a;
    apples.push_back(make_pair(a, i));
  }
  
  vector<char> naive(n);
  ull naived;
  {
    ull u = 0;
    ull m = 0;
    for (int i = 0; i < n; i++) {
      auto a = apples[i];
      if (u > m) {
	naive[i] = '2';
	m += a.first;
      } else {
	naive[i] = '1';
	u += a.first;
      }
    }
    naived = min(u-m, m-u);
  }
  vector<char> sorted(n);
  ull sortedd = 1ull<<60;
  {
    sort(apples.begin(), apples.end());
    ull u = 0;
    ull m = 0;
    for (int i = n-1; i >= 0; i--) {
      auto a = apples[i];
      if (u > m) {
	sorted[a.second] = '2';
	m += a.first;
      } else {
	sorted[a.second] = '1';
	u += a.first;
      }
    }
    sortedd = min(u-m, m-u);
  }
  
  vector<char> bitthing(n);
  ull bitthingd = 1ull<<60;
  {
    const int bits = min(n, 20);
    for (int k = 0; k < (1<<bits); k++) {
      ull u = 0;
      ull m = 0;
      int i = n-1;
      for (int j = 0; j < bits; j++, i--) {
	auto a = apples[i];
	if (k & (1<<j)) {
	  sorted[a.second] = '2';
	  m += a.first;
	} else {
	  sorted[a.second] = '1';
	  u += a.first;
	} 
      }
      for (; i >= 0; i--) {
	auto a = apples[i];
	if (u > m) {
	  sorted[a.second] = '2';
	  m += a.first;
	} else {
	  sorted[a.second] = '1';
	  u += a.first;
	}
      }
      sortedd = min(u-m, m-u);
    }
  }
  
  if (naived < sortedd && naived < bitthingd) {
    print(naive);
  } else if (sortedd < naived && sortedd < bitthingd) {
    print(sorted);
  } else if (bitthingd < naived && bitthingd < sortedd) {
    print(bitthing);
  } else {
    print(sorted);
  }
}

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