Split in Three

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ppb pop_back
#define x first
#define y second
#define int long long
#define mp make_pair

using namespace std;

const int inf = 1e18, sz = 4105;

int ans[sz];

int used[sz][sz];

signed main (){
//    cin.tie(0);
//    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int d = (n*(n+1))/2;
    if (d % 3 != 0) cout << "IMPOSSIBLE";
    else {
         d /= 3;
         used[0][0] = -1;
         for (int i = 1; i <= n; ++i){
             for (int j = d+5; j >= 0; --j){
                for (int z = d+5; z >= 0; --z){
                    if (used[j][z] == 0){
                        if (j >= i && used[j - i][z]) used[j][z] = i;
                        else if (z >= i && used[j][z - i]) used[j][z] = -i;
                    }
                    }
            }
        }
//        cout << "norm" << '\n';
        int x = d - 1, y = d;
        while (x != 0 || y != 0){
            if (used[x][y] > 0) {
                ans[used[x][y]] = 1;
                x -= used[x][y];
            }
            else {
                ans[abs(used[x][y])] = 2;
                y -= abs(used[x][y]);
            }
        }
        for (int i = 1; i <= n; ++i){
            if (ans[i] != 0) cout << ans[i] << ' ';
            else cout << 3 << ' ';
        }
    }
    return 0;
}

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