Split in Three

#include <bits/stdc++.h>

#define int long long

using namespace std;

map<pair<int,int>,bool> dp[5005];
map<pair<int,int>,int> to[5005];
int n;
bool rec(int a, int b, int c, int cur) {
    if (dp[a].count({b,c}) != 0) return dp[a][{b,c}];
    if (cur == n+1) {
        if (b == a+1 && b == c-1) return true;
        else return false;
    }
    bool res = false;
    if (rec(a+cur,b,c,cur+1)) {
        res = true;
        to[a][{b,c}] = 1;
    } else if (rec(a,b+cur,c,cur+1)) {
        res = true;
        to[a][{b,c}] = 2;
    } else if (rec(a,b,c+cur,cur+1)) {
        res = true;
        to[a][{b,c}] = 3;
    }
    dp[a][{b,c}] = res;
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    bool res = rec(0,0,0,1);
    if (!res) {
        cout << "IMPOSSIBLE\n";
        exit(0);
    }
    int a = 0, b = 0, c = 0;
    for (int i = 1; i <= n; i++) {
        int x = to[a][{b,c}];
        cout << x << ' ';
        if (x == 1) a += i;
        else if (x == 2) b += i;
        else c += i;
    }
    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: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 2

Verdict: TIME LIMIT EXCEEDED