Split in Three

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e5 + 5;
const ll mo = 1e9 + 7;
ll n;
ll d[110][10101];
ll a[NN];
void gagal()
{
    cout << "IMPOSSIBLE\n";
    exit(0);
}
ll depe(ll pos, ll jum)
{
    if(jum < 0)
        return 0;
    if(jum == 0)
        return 1;
    if(pos > n)
        return 0;
    ll ret = d[pos][jum];
    if(ret == -1)
    {
        ret = 0;
        if(a[pos] == 0 && depe(pos + 1, jum - pos))ret = 1;
        if(depe(pos + 1, jum))ret = 1;
        d[pos][jum] = ret;
    }
    return ret;
}
void pc(ll pos, ll jum, ll isi)
{
    if(jum == 0)
        return ;
    if(depe(pos + 1, jum))pc(pos + 1, jum, isi);
    else
    if(a[pos] == 0 && depe(pos + 1, jum - pos))
    {
        a[pos] = isi;
        pc(pos + 1, jum - pos, isi);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    ll sum = n * (n + 1) / 2;
    if(sum % 3 != 0)
        gagal();
 
    memset(d, -1, sizeof(d));
    pc(1, sum / 3 - 1, 1);
 
    memset(d, -1, sizeof(d));
    pc(1, sum / 3, 2);
 
    memset(d, -1, sizeof(d));
    pc(1, sum / 3 + 1, 3);
 
    for(ll i = 1; i <= n; i++)
    {
        cout << a[i];
        if(i < n)
            cout << " ";
        else
            cout << "\n";
    }
}

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