Split in Three

input/code.cpp: In function 'int main()':
input/code.cpp:14:7: warning: unused variable 'a' [-Wunused-variable]
   int a[n];
       ^
input/code.cpp:20:24: warning: unused variable 'y' [-Wunused-variable]
   int x = sum / 3 - 1, y = sum / 3, z = sum / 3 + 1;
                        ^
input/code.cpp:20:37: warning: unused variable 'z' [-Wunused-variable]
   int x = sum / 3 - 1, y = sum / 3, z = sum / 3 + 1;
                                     ^

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define all(x) (x).begin(),(x).end()
#define pb push_back

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  int ans[n];
  fill(ans, ans + n, 0);
  int a[n];
  int sum = n * (n + 1) / 2;
  if(sum % 3) {
    cout << "IMPOSSIBLE\n";
    return 0;
  }
  int x = sum / 3 - 1, y = sum / 3, z = sum / 3 + 1;
  if(x == 0) {
    cout << "IMPOSSIBLE\n";
    return 0;
  }
  if(n % 3 == 0) {
    int div = n / 3;
    int perm[3] = {1, 2, 3};
    for(int i = 0; i + 6 <= n; i += 6) {
      for(int j = 0; j < 2; ++j) {
        for(int k = 0; k < 3; ++k) {
          ans[i + j * 3 + k] = perm[k];
        }
        swap(perm[0], perm[2]);
      }
    }
    if(div % 2 == 0) {
      ans[0] = 3;
    } else {
      for(int i = n - 3; i < n; ++i) {
        ans[i] = perm[i - (n - 3)];
      }
    }
    for(int i = 0; i < n; ++i) {
      cout << ans[i] << " ";
    }
    cout << "\n";
  } else {
    ans[0] = 2;
    ans[1] = 3;
    int perm[3] = {2, 1, 3};
    for(int i = 2; i < n; i += 3) {
      for(int j = i; j <= i + 2; ++j) {
        ans[j] = perm[2 - (j - i)];
      }
      rotate(perm, perm + 1, perm + 3);
    }
    int sum[4];
    fill(sum, sum + 4,0);
    for(int i = 0; i < n; ++i) {
      sum[ans[i]] += i + 1;
    }
    if(sum[1] == sum[2] && sum[2] == sum[3]) {
      --sum[ans[0]];
      ans[0]++;
      if(ans[0] == 4) ans[0] = 1;
      ++sum[ans[0]];
    }
    vector<array<int, 2>> p;
    for(int i = 1; i <= 3; ++i) {
      p.pb({sum[i], i});
    }
    sort(all(p));
    for(int i = 0; i < n; ++i) {
      ans[i] = p[ans[i] - 1][1];
      cout << ans[i] << " ";
    }
    cout << "\n";
  }
}

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