Split in Three

#include <iostream>
#define MAXM 1750

using namespace std;

char dp[101][MAXM][MAXM];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int m = n * (n + 1) / 2;
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < MAXM; j++) {
            for (int k = 0; k < MAXM; k++) {
                if (dp[i - 1][j][k]) dp[i][j][k] = 3;
                else if (j >= i && dp[i - 1][j - i][k]) dp[i][j][k] = 1;
                else if (k >= i && dp[i - 1][j][k - i]) dp[i][j][k] = 2;
            }
        }
    }
    if (m % 3 != 0 || !dp[n][m / 3 - 1][m / 3]) cout << "IMPOSSIBLE";
    else {
        int j = m / 3 - 1, k = m / 3;
        int ans[n];
        for (int i = n; i > 0; i--) {
            ans[i - 1] = dp[i][j][k];
            if (ans[i - 1] == 1) j -= i;
            else if (ans[i - 1] == 2) k -= i;
        }
        for (int i = 0; i < n; i++) cout << ans[i] << " ";
    }
    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