Omenat

#include <iostream>
#include <cstdlib>
#include <vector>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 8e6;
ll t[111];
ll mod = 98765431;
ll asd = 1007;
int main() {
    srand(time(0));
    ll rr = rand()%mod;
    int n;
    cin>>n;
    pair<ll, vector<int> > best = {1e18, {0}};
    ll sum = 0;
    for(int i = 0; i < n; ++i) {
        cin>>t[i];
        sum += t[i];
    }
    for(int i = 0; i < N/n; ++i) {
        ll a = sum/2;
        ll left = sum;
        vector<int> v(n);
        for(int j = 0; j < n; ++j) {
            rr *= asd;
            rr %= mod;
            ll r = rr%1000;
            //if(r/1000 < a/left) {
            if(r*left < 1000*a) {
                left -= t[j];
                a -= t[j];
                v[j] = 1;
            }
            else {
                left -= t[j];
                v[j] = 2;
            }
        }
        a = abs(a);
        best = min(best, {a, v});
    }
    for(int i = 0; i < n; ++i) {
        cout<<best.S[i]<<' ';
    }
    cout<<'\n';
}

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