Split in Three

input/code.cpp: In function 'int main()':
input/code.cpp:64:8: warning: unused variable 'a' [-Wunused-variable]
     ll a,b,c,d;
        ^
input/code.cpp:64:10: warning: unused variable 'b' [-Wunused-variable]
     ll a,b,c,d;
          ^
input/code.cpp:64:12: warning: unused variable 'c' [-Wunused-variable]
     ll a,b,c,d;
            ^
input/code.cpp:64:14: warning: unused variable 'd' [-Wunused-variable]
     ll a,b,c,d;
              ^

#pragma GCC optimize("O3")   //
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);

ll random2(){
    return (1ll << 31ll)*eng()+eng();
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 400002;

ll F[3] = {0};

int ANS[101] = {0};

void give(int x, int rem){
    F[rem] += x;
    ANS[x] = rem;
}

vi P;

void solve(int start, int stop){
    for(int c1 = start; c1 <= stop; c1++){
        int b = ((c1-start)/3)%3;
        int rem = ((c1-1)-b+3)%3;
        give(c1, P[rem]);
    }
}


bool comp(ll i, ll j){
    return F[i] < F[j];
}

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

    //freopen("fhc.txt","r",stdin);
    //freopen("autput.txt","w",stdout);

    ll a,b,c,d;

    P = {0,1,2};
    vi P2 = {0,1,2};
    cin >> n;
    if(n%3 == 1){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    if(n%3 == 0){
        solve(1, n);

        if(n%9 == 0){
            rep(c1,1,n){
                if(ANS[c1] == 2 && ANS[c1+1] == 0){
                    give(c1,0);
                    give(c1+1,2);
                    F[2] -= c1;
                    F[0] -= c1+1;
                    break;
                }
            }
        }

        sort(all(P), comp);

        rep(c1,0,3){
            P2[P[c1]] = c1;
        }

        cerr << F[0] << " " << F[1] << " " << F[2] << "   gfd\n";
        rep(c1,1,n+1){
            cout << P2[ANS[c1]]+1 << " ";
        }cout << "\n";
    }
    if(n%3 == 2){
        solve(3, n);

        sort(all(P), comp);
        give(2,P[0]);
        give(1,P[2]);
        sort(all(P), comp);

        rep(c1,0,3){
            P2[P[c1]] = c1;
        }

        cerr << F[0] << " " << F[1] << " " << F[2] << "   gfd\n";
        rep(c1,1,n+1){
            cout << P2[ANS[c1]]+1 << " ";
        }cout << "\n";
    }

    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

1 2 3   gfd

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

4 6 5   gfd

Test 4

Group: 1, 2

Verdict: ACCEPTED

6 8 7   gfd

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

13 11 12   gfd

Test 7

Group: 1, 2

Verdict: ACCEPTED

14 15 16   gfd

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

300 302 301   gfd

Test 10

Group: 2

Verdict: ACCEPTED

1519 1521 1520   gfd

Test 11

Group: 2

Verdict: ACCEPTED

1551 1553 1552   gfd

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

1618 1616 1617   gfd

Test 14

Group: 2

Verdict: ACCEPTED

1649 1650 1651   gfd

Test 15

Group: 2

Verdict: ACCEPTED