[sg function] lightoj Partitioning Game

Yes $n$ Rubble , You can choose to divide one pile into The quantity is different Two piles of , And it must be divided once . Players who can't score any more lose .

The necessary state in the initial state ：$sg[0]=sg[1]=sg[2]=0$, Then enumerate each stacking method SG Just watch .

Be careful , In seeking MEX Don't use tape when log Data structure of ( such as std::set), Will timeout …

#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int N = 1e4 + 10;
int sg[N], mex[N];

#define win cout << "Alice" << endl
#define lose cout << "Bob" << endl

inline void getsg(){
    
    memset(sg, -1, sizeof(sg));
    sg[0] = sg[1] = sg[2] = 0;
    for(int i = 3; i <= N; i++){
    
        memset(mex, 0, sizeof mex);
        for(int j = 1; j * 2 < i; j++){
    
            mex[sg[j] ^ sg[i - j]]++;
        }
        int mexv = 0;
        while(mex[mexv]) mexv++;
        sg[i] = mexv;
    }
}

inline void solve(int cas){
    
    cout << "Case " << cas << ": ";
    int n = 0; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
    
        int x; cin >> x;
        if(i == 1) ans = sg[x];
        else ans ^= sg[x];
    }
    if(ans) win;
    else lose;
}

signed main(){
    
    getsg();
    int t = 0; cin >> t;
    for(int i = 1; i <= t; i++) solve(i);
    return 0;
}