Omenat

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <sstream>

typedef long long LL;
using namespace std;

int main(){
    srand(time(0));
    LL n; cin >> n;
    vector<LL> v;
    LL all = 0;
    
    for(int i = 0; i < n; i++){
        LL x; cin >> x;
        all += x;
        v.push_back(x);
    }
    LL target = all/2;
    
    set<LL> solution;
    LL sum = 0;
    for(int i = 0; i < n/2; i++){
        solution.insert(i);
        sum += v[i];
    }
    
    LL rounds = 8 * 1e6;
    LL best = 1e15;
    set<LL> best_solution = solution;
    
    for(int rep = 0; rep <= rounds; rep++){
        LL k = rand() % n;
        if(solution.count(k)){
            if(abs(target - (sum - v[k])) < abs(target - sum) || rand()%100 < 10){
                solution.erase(k);
                sum -= v[k];
            } 
        } else{
            if(abs(target - (sum -+v[k])) < abs(target - sum) || rand()%100 < 10){
                solution.insert(k);
                sum += v[k];
            }
        }
        if(abs(sum - target) < best){
            best = abs(sum - target);
            best_solution = solution;
        }
    }
    for(int i = 0; i < n; i++){
        if(best_solution.count(i)) cout << "1 ";
        else cout << "2 ";
    }
    cout << endl;
    
}

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