Split in Three

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <cstring>
#include <unordered_set>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<pair<int,int>>;
using vb = vector<bool>;
template<typename T>
using Graph = vector<vector<T>>;

struct State
{
	int i, a, b;
	bool operator== (const State& state) const
	{
		return i == state.i && a == state.a && b == state.b;
	}
};

struct StateHash
{
	size_t operator() (const State& state) const
	{
		size_t res = state.a;
		res |= state.b << 8;
		res |= state.i << 16;
		return res;
	}
};

int n, mx, done, total;
vi state;
//set<pair<int, ii>> visited;
unordered_set<State, StateHash> visited;

void run(int i, int a, int b)
{
	int c = total - a - b;
	if(a > mx || b > mx || a > c || b > c) return;
	
	int tn = min(a, b);
	int tm = max(a, b);
	a = tn;
	b = tm;

	State s { i, a, b };
	if(visited.count(s)) return;
	visited.insert(s);
	
//	cout << a << ' ' << b << ' ' << c << '\n';
	if(a + 1 == b && b + 1 == c)
	{
		done = 1;
		return;
	}

	if(i > n) return;

	state[i] = 1;
	run(i + 1, a + i, b);
	if(done) return;

	state[i] = 2;
	run(i + 1, a, b + i);
	if(done) return;

	state[i] = 3;
	run(i + 1, a, b);
}

void solve() 
{
	cin >> n;
	state.assign(n + 1, 3);
	
	total = n * (n + 1) / 2;
	mx = (total + 2) / 3;

	run(1, 0, 0);
	if(!done)
	{
		cout << "IMPOSSIBLE\n";
		return;
	}
	for(int i = 1; i <= n; ++i)
	{
		cout << state[i] << ' ';
	}
	cout << '\n';
}

int main () 
{
#ifdef LOCAL
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif

   	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc = 1; 
//	cin >> tc;
	while(tc--) solve();
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: WRONG ANSWER

Test 7

Group: 1, 2

Verdict: WRONG ANSWER

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: WRONG ANSWER

Test 14

Group: 2

Verdict: WRONG ANSWER

Test 15

Group: 2

Verdict: TIME LIMIT EXCEEDED