Split in Three

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void Solve() {
	int n;
	cin >> n;
	int total = n * (n + 1) / 2;
	if(total % 3 != 0) {
		cout << "IMPOSSIBLE\n";
		return;
	}
	int maxNeed = total / 3;
	bool dp[maxNeed][maxNeed + 1][maxNeed + 2];
	for(int i = 0; i < maxNeed; i++) {
		for(int j = 0; j <= maxNeed; j++) {
			for(int k = 0; k <= maxNeed + 1; k++) {
				dp[i][j][k] = false;
			}
		}
	}
	dp[0][0][0] = true;
	for(int cur = 1; cur <= n; cur++) {
		for(int i = 0; i < maxNeed; i++) {
			for(int j = 0; j <= maxNeed; j++) {
				for(int k = 0; k <= maxNeed + 1; k++) {
					if(i >= cur && dp[i - cur][j][k]) {
						dp[i][j][k] = true;
						continue;
					}
					if(j >= cur && dp[i][j - cur][k]) {
						dp[i][j][k] = true;
						continue;
					}
					if(k >= cur && dp[i][j][k - cur]) {
						dp[i][j][k] = true;
					}
				}
			}
		}
	}
	if(!dp[maxNeed - 1][maxNeed][maxNeed + 1]) {
		cout << "IMPOSSIBLE\n";
		return;
	}
	int curI = maxNeed - 1, curJ = maxNeed, curK = maxNeed + 1;
	vector<int> ans(n + 1);
	for(int cur = n; cur > 0; cur--) {
		if(curI >= cur && dp[curI - cur][curJ][curK]) {
			ans[cur] = 1;
			curI -= cur;
			continue;
		}
		if(curJ >= cur && dp[curI][curJ - cur][curK]) {
			ans[cur] = 2;
			curJ -= cur;
			continue;
		}
		ans[cur] = 3;
		curK -= cur;
	}
	for(int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	cout << "\n";
}
 
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
}

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: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: RUNTIME ERROR

Test 11

Group: 2

Verdict: RUNTIME ERROR

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: RUNTIME ERROR

Test 14

Group: 2

Verdict: RUNTIME ERROR

Test 15

Group: 2

Verdict: ACCEPTED