C++ Realize coloring game (Game)

On a 2*N grid, Alice and Bob begin their new game journey.

One of these cells has already been colored, and Alice and Bob take turns coloring these cells, using two coloring tools: the first can be colored on any of the cells, and the second can be colored on any of the 2*2 cells. In each round of the game, they can choose one tool to paint the unstained squares. It should be noted that all 4 cells should not be colored when coloring 2*2 cells. The player who fills all the squares in the last step wins.

1 as always, Alice first mover, optimal strategy, who is the winner?
Input enters behavior 1, T, to indicate that there is T group test data.
Each set contains two Numbers, N and M, and M represents how many cells have been stained. The next M lines have two digits each, Xi and Yi, representing the grid coordinates that have been painted.

[Technical Specification]

1. 1 < = T < = 74
2. 1 < = N < = 4747
3. 0 < = M < = 2 * N
4. 1 < = Xi < = 2, 1 < = Yi < = N, grid coordinates do not repeat
For each set of data, Output outputs the first set of data, then "Alice" or "Bob" to indicate the winner of the game. Sample Input
2
2 0
2 2
1 1
2 2
Sample Output
Case 1: Alice
Case 2: Bob

Ideas:

Consider the value of sg for Spaces with consecutive n columns.

When n=0, it is clear that sg[0]=0, and then the ordinary sg function is tabbed, but to partition the grid.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn=5000;
int sg[maxn];
bool pl[2][maxn];
int get_sg(int x)
{
 if(sg[x]!=-1)
  return sg[x];
 bool vis[maxn];
 memset(vis, false , sizeof(vis));
 for(int i=0; i<=x-1-i; i++)
 {
  int t=get_sg(i)^1^get_sg(x-1-i); // Only with this 1 Columns of 1 A grid 
  vis[t]=true;
 }
 for(int i=0; i<=x-2-i; i++)
 {
  int t=get_sg(i)^get_sg(x-i-2); // this 1 Paint all the columns 
  vis[t]=true;
 }
 for(int i=0; ; i++)
 {
  if(!vis[i])
  {
   sg[x]=i;
   break;
  }
 }
 return sg[x];
}
int main()
{
 memset(sg, -1, sizeof(sg));
 sg[0]=0;
 for(int i=1; i<maxn; i++)
  sg[i]=get_sg(i);
 int t;
 scanf("%d", &t);
 for(int cas=1; cas<=t; cas++)
 {
  int n, m;
  scanf("%d%d", &n, &m);
  memset(pl, false, sizeof(pl));
  int ans=0;
  for(int i=1; i<=m; i++)
  {
   int x, y;
   scanf("%d%d", &x, &y);
   pl[--x][--y]=true; 
  }
  int cnt=0;
  for(int i=0; i<n; i++) // Partition the grid 
  {
   if(pl[0][i]&&pl[1][i])  // If a 1 The columns are all painted, so it's different or this 1 Of or pertaining to a continuous space preceding a column grid sg value 
   {
    ans^=sg[cnt];
    cnt=0;
    continue;
   }
   if(pl[0][i]^pl[1][i]) // If this 1 A list of paint 1 A grid, so different or this 1 Of or pertaining to a continuous space preceding a column grid sg Value of exclusive or again 1
   {
    ans=ans^sg[cnt]^1;
    cnt=0;
    continue;
   }
   cnt++;  // If this 1 The length of successive Spaces in a column without a grid being painted +1
  }
  ans^=sg[cnt];
  if(ans)
   printf("Case %d: Alice\n", cas);
  else
   printf("Case %d: Bob\n", cas);
 }
 return 0;
}