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<ull> 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(a);
  }
  
  vector<char> naive(n);
  ull naived;
  {
    ull u = 0;
    ull m = 0;
    for (int i = 0; i < n; i++) {
      ull a = apples[i];
      if (u > m) {
	naive[i] = '2';
	m += a;
      } else {
	naive[i] = '1';
	u += a;
      }
    }
    naived = min(u-m, m-u);
  }
  vector<char> sorted(n);
  ull sortedd;
  {
    sort(apples.begin(), apples.end());
    ull u = 0;
    ull m = 0;
    for (int i = n-1; i >= 0; i++) {
      ull a = apples[i];
      if (u > m) {
	sorted[i] = '2';
	m += a;
      } else {
	sorted[i] = '1';
	u += a;
      }
    }
    sortedd = min(u-m, m-u);
  }
  
  vector<char> random;
  ull randomd = 1ull<60;
  {
    for (int j = 0; j < 100000; j++) {
      vector<char> cur(n);
      ull u = 0;
      ull m = 0;
      for (int i = 0; i < n; i++) {
	ull a = apples[i];
	if (flip(mt)) {
	  cur[i] = '1';
	  u += a;
	} else {
	  cur[i] = '2';
	  m += a;
	}
      }
      
      ull t = min(u-m, m-u);
      if (t < randomd) {
	randomd = t;
	random = cur;
      }
    }
  }
  
  if (naived < sortedd && naived < randomd) {
    print(naive);
  } else if (sortedd < naived && sortedd < randomd) {
    print(sorted);
  } else if (randomd < naived && randomd < sortedd) {
    print(random);
  } else {
    print(sorted);
  }
}

Test 1

Verdict: RUNTIME ERROR

Test 2

Verdict: RUNTIME ERROR

Test 3

Verdict: RUNTIME ERROR

Test 4

Verdict: RUNTIME ERROR

Test 5

Verdict: RUNTIME ERROR

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: RUNTIME ERROR

Test 10

Verdict: RUNTIME ERROR