Split in Three

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
//#include <cmath>
//#include <numeric>
//#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

int N;
int sum;
int target;

unsigned char memo[100][1650][1651];

bool go(int n = 1, int sum1 = 0, int sum2 = 0) {
   if (n > N)
      return sum1 == target-1 && sum2 == target;
   if (sum1 > target-1 || sum2 > target)
      return false;
   unsigned char& res = memo[n-1][sum1][sum2];
   if ((res & 1) == 0) {
      res = 1;
      if (go(n+1, sum1+n, sum2)) {
         res |= 1<<1 | 1<<2;
      }
      else if (go(n+1, sum1, sum2+n)) {
         res |= 1<<1 | 2<<2;
      }
      else if (go(n+1, sum1, sum2)) {
         res |= 1<<1 | 3<<2;
      }
   }
   return (res >> 1) & 1;
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   cin >> N;
   sum = N*(N+1)/2;
   if ((sum % 3) != 0) {
      cout << "IMPOSSIBLE\n";
      return 0;
   }

   target = sum / 3;

   bool res = go();
   if (res) {
   // cerr << "POSSIBLE\n";
      for (int n = 1, sum1 = 0, sum2 = 0; n <= N; ++n) {
         unsigned char m = memo[n-1][sum1][sum2];
         assert((m >> 1) & 1);
         int g = (m >> 2);
         cout << g << ' ';
         if (g == 1)
            sum1 += n;
         else if (g == 2)
            sum2 += n;
         else
            assert(g == 3);
      }
      cout << '\n';
   }
   else
      cout << "IMPOSSIBLE\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