Split in Three

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })
 
vl solve(ll n) {
	ll sum = n*(n+1)/2;
	if (sum%3 != 0) return {};
	sum /= 3;
 
	assert(n%3 != 1);
 
	if (n <= 12) {
		FOR(mask,0,1 << n) {
			for (ll smask = mask; smask > 0; smask = (smask-1) & mask) {
				vl res(n);
				FOR(i,0,n) {
					if (smask & (1 << i)) res[i] = 1;
					else if (mask & (1 << i)) res[i] = 2;
					else res[i] = 3;
				}
				vl total(4);
				FOR(i,0,n) total[res[i]] += i+1;
 
				if (total[1] == sum-1 && total[2] == sum && total[3] == sum+1) {
					return res;
				}
			}
		}
		return {};
	} else {
		ll m = n;
		while (m >= 12) m -= 6;
		
		vl res = solve(m);
		assert(sz(res) == m);
		res.resize(n);
		while (m < n) {
			res[m] = res[m+5] = 1;
			res[m+1] = res[m+4] = 2;
			res[m+2] = res[m+3] = 3;
			m += 6;
		}
		return res;
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	ll n; cin >> n;
 
	{
		vl v = solve(n);
		for (ll x: v) cout << x << " ";
		if (v.empty()) cout << "IMPOSSIBLE";
		cout << endl;
	}
}
 

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