#include "prison.h"

#include <algorithm>
#include <functional>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> devise_strategy(int N) {
  vector<int> dp = { 2 };
  vector<vector<int> > dp_path = { vector<int>() };
  for (int i = 1; dp.back() < N; i++) {
    dp.push_back(0);
    dp_path.push_back(vector<int>());
    for (int j = i - 1; j >= 0; j--) {
      if (dp[i] < (i - j) * dp[j] + 2) {
        dp[i] = (i - j) * dp[j] + 2;
        dp_path[i] = dp_path[j];
        dp_path[i].push_back(i - j);
      }
    }
  }
  vector<int> splits = dp_path.back();
  reverse(splits.begin(), splits.end());
  int b = splits.size();
  vector<string> vals;
  function<void(int, string)> generate = [&](int depth, string str) {
    vals.push_back(str + string(b - depth + 1, 'L'));
    if (depth != b) {
      for (int ch = 0; ch < splits[depth]; ch++) {
        generate(depth + 1, str + char(ch + '0'));
      }
    }
    vals.push_back(str + string(b - depth + 1, 'R'));
  };
  generate(0, "");
  vector<int> cs(dp.back() + 1), ct(dp.back());
  int sum = 1;
  for (int i = 0; i < b; i++) {
    for (int j = 0; j < splits[i]; j++) {
      cs[sum + j] = i + 1;
      ct[sum + j] = j;
    }
    sum += splits[i];
  }
  vector<vector<int>> ret(sum, vector<int>(N+1, 0));
  for (int i = 0; i < sum; i++) {
    int s = cs[i], t = ct[i];
    ret[i][0] = (s % 2);
    for (int j = 0; j < N; j++) {
      int xbit = (s != 0 ? t : -1);
      int ybit = (s != 0 && vals[j][s - 1] != 'L' && vals[j][s - 1] != 'R' ? vals[j][s - 1] - '0' : -1);
      if (vals[j][s - 1] == 'L') {
        ret[i][j+1] = (s % 2 == 1 ? -2 : -1);
      }
      else if (vals[j][s - 1] == 'R') {
        ret[i][j+1] = (s % 2 == 1 ? -1 : -2);
      }
      else if (xbit < ybit) {
        ret[i][j+1] = (s % 2 == 1 ? -1 : -2);
      }
      else if (xbit > ybit) {
        ret[i][j+1] = (s % 2 == 1 ? -2 : -1);
      }
      else if (vals[j][s] == 'L') {
        ret[i][j+1] = (s % 2 == 1 ? -2 : -1);
      }
      else if (vals[j][s] == 'R') {
        ret[i][j+1] = (s % 2 == 1 ? -1 : -2);
      }
      else {
        ret[i][j+1] = (s != 0 ? i - t + splits[s - 1] : 1) + int(vals[j][s] - '0');
      }
    }
  }
  return ret;
}