POJ 3537 Crosses and Crosses

Problem Description:
Two players take turn in playing a game on a 1 x N board.
When it is a player's turn, he puts a marker on a grid that had no marker.
If after a movement there are 3 consecutive markers on the board, the player who made that movement wins the game.

Constraints:
1 ≤ N ≤ 2000

Solution:
Obviously, both player will avoid putting marker so that there is "VV_" or "V_V".
Hence a movement is equivalent to splitting the board into two independent games, where two grids left and two grids right will and itself will be eliminated from the game.

Code:

#include <iostream>
#include <cstring>
#include <vector>

int dp[2000 + 1];

int grundy(int n) {
  if (n <= 0) return 0;
  if (~dp[n]) return dp[n];
  std::vector<int> vis(1 << 11);
  for (int i = 1; i <= n; ++i) {
    vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;
  }
  for (int i = 0; ; ++i) {
    if (!vis[i]) return dp[n] = i;
  }
}

signed main() {
  std::memset(dp, 0xff, sizeof(dp));
  std::ios::sync_with_stdio(false);
  int n;
  std::cin >> n;
  std::cout << (grundy(n) ? 1 : 2) << std::endl;
  return 0;
}