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;
  {
    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> 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++) {
	auto a = apples[i];
	if (flip(mt)) {
	  cur[a.second] = '1';
	  u += a.first;
	} else {
	  cur[a.second] = '2';
	  m += a.first;
	}
      }
      
      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: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER