Split in Three

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1650;
const int M = 100;
int dp[N][N];
int sol[M];
 
 
int main(){
    int n;
    cin >> n;
    if(n % 3 == 1){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    int A = (n * (n + 1) / 2 - 3) / 3;
    int A1 = A + 1;
    dp[0][0]=-1;
    int i1, i2;
    for(int i = 1; i <= n; i ++ ){
        i1 = min(A, i * (i - 1) / 2);
        i2 = min(A1, i * (i - 1) / 2);
        for(int p = i1 ; p >= 0 ; p -- ){
            for(int q = i2; q >= 0; q -- ){
                if(dp[p][q] != 0){
                    if(p + i <= A && dp[p + i][q] == 0){
                        dp[p + i][q] = i;
                    }
                    if(q + i <= A1 && dp[p][q + i] == 0){
                        dp[p][q + i] = -i;
                    }
                }
            }
        }
    }
    int ii = A;
    int jj = A1;
    if(dp[ii][jj] == 0){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    int num;
    while(ii > 0 || jj > 0){
        num = dp[ii][jj];
        if(num > 0){
            sol[num]=1;
            ii -= num;
        }
        else{
            sol[-num]=2;
            jj -= -num;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        if(sol[i] == 0) sol[i]=3;
        cout << sol[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: TIME LIMIT EXCEEDED

Test 15

Group: 2

Verdict: ACCEPTED