Split in Three

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(a) (int)a.size()
#define pb push_back
#define int unsigned long long

using namespace std;
typedef long long ll;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

bitset <6000> b[110];

int used[110];

void solve() {
    int n;
    cin >> n;
    if ((n * (n + 1) / 2) % 3 != 0) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    b[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        b[i] = (b[i - 1] | (b[i - 1] << i));
        used[i] = 3;
    }
    int x = (n * (n + 1) / 2 - 3) / 3;
    if (!b[n][x]) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = n; i > 0; --i) {
        if (x >= i && b[i - 1][x - i]) {
            used[i] = 1;
            x -= i;
        }
    }
    x = (n * (n + 1) / 2 - 3) / 3 + 1;
    if (!b[n][x]) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = n; i > 0; --i) {
        if (used[i] == 1)
            continue;
        if (x >= i && b[i - 1][x - i]) {
            used[i] = 2;
            x -= i;
        }
    }
    if (x != 0) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    for (int i = 1; i <= n; ++i) {
        cout << used[i] << " ";
    }
    return;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED