Kolmijako

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define ull unsigned long long

using namespace std;

vector<int> used(101, 0);

bool haku(ll sum, ll below, ll target1, int x) {
	if (sum == target1) return true;

	for (ll i = below - 1; i >= 1; i--) {
		if (!used[i]) {
			if (i + sum <= target1) {
				used[i] = x;
				if (haku(i + sum, i, target1, x)) {
					return true;
				}
				used[i] = 0;
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	//istringstream cin(R"(4)");

	ll n; cin >> n;

	ll target = (n * (n + 1))/2/3;

	if (((n * (n + 1)) / 2) % 3 != 0) {
		cout << "IMPOSSIBLE";
		return 0;
	}

	haku(0, n + 1, target-1, 1);
	haku(0, n + 1, target, 2);
	haku(0, n + 1, target+1, 3);

	for (int i = 1; i <= n; i++) {
		cout << used[i] << " ";
	}

}

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