Split in Three

#include <bits/stdc++.h>

#define ll long long
#define what_is(a) cout << #a << " is " << a << "\n";
#define check(a) cout << "reached " << a << "\n";

using namespace std;

int main(){
	int n;
	cin >> n;
	ll r = 0;
	for(int i=0;i<n;i++)r+=i+1;
	if((r-3)%3!=0){
		//check(1)
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	int a = (r-3)/3;
	int mem[n+1];
	memset(mem,0,sizeof(mem));
	r = 0;
	for(int i=n;i>=1;i--){
		if(mem[i]!=0)continue;
		if(i+r<=a)r+=i,mem[i]=1;
	}
	if(r!=a){
		//check(2)
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	r=0,a++;
	for(int i=n;i>=1;i--){
		if(mem[i]!=0)continue;
		if(i+r<=a)r+=i,mem[i]=2;
	}
	if(r!=a){
		//check(3)
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	r=0,a++;
	for(int i=n;i>=1;i--){
		if(mem[i]!=0)continue;
		if(i+r<=a)r+=i,mem[i]=3;
	}
	if(r!=a){
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	for(int i=1;i<=n;i++)cout << mem[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