Split in Three

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const int MAX_N = 100, MAX_K = 2000;
int sum[3];
int sol[1 + MAX_N];
 
namespace brut {
    using ll = long long;
    const int MAX_N = 100;
    int p3[1 + MAX_N];
 
    int main (int n) {
        int rest = n % 6;
        if (rest < 6)
            rest += 6;
        rest = min (rest, n);
        p3[0] = 1;
        for (int i = 1; i <= rest; i++)
            p3[i] = p3[i - 1] * 3;
        vector <int> values (n + 1);
        for (int i = n; i > rest; i--) {
            int bucket = 2 - (n - i) % 3;
            int inv = ((n - i) / 3) & 1;
            if (inv)
                bucket = 2 - bucket;
            values[i] = bucket + 1;
        }
        for (int mask = 0; mask < p3[rest]; mask++) {
            vector <int> sum (3, 0);
            for (int pos = 0; pos < rest; pos++) {
                int bucket = (mask / p3[pos]) % 3;
                sum[bucket] += pos + 1;
                values[pos + 1] = bucket + 1;
            }
            if (sum[0]  + 1 == sum[1] && sum[1] + 1 == sum[2]) {
                for (int i = 1; i <= n; i++)
                    cout << values[i] << " ";
                cout << "\n";
                return 1;
            }
        }
        cout << "IMPOSSIBLE\n";
        return 0;
    }
}
 
int main () {
    int n;
    cin >> n;
    brut::main (n);
    return 0;
}

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