1
class Solution {
2
 public:
3
  int helper(unsigned long s, unsigned long n0, unsigned long n1, unsigned long n2, int turn) {
4
    if (n0 == 0 && n1 == 0 && n2 == 0) return 1;
5

6
    int next_turn = 1 ^ turn;
7
    int tmp = next_turn;
8

9
    if (s == 0) {
10
      if (n1 || n2) {
11
        if (n1) tmp = helper(1, n0, n1 - 1, n2, next_turn);
12
        if (tmp != turn && n2) tmp = helper(2, n0, n1, n2 - 1, next_turn);
13
      }
14
    } else if (s == 1) {
15
      if (n0 || n1) {
16
        if (n0) tmp = helper(1, n0 - 1, n1, n2, next_turn);
17
        if (tmp != turn && n1) tmp = helper(2, n0, n1 - 1, n2, next_turn);
18
      }
19
    } else {
20
      if (n0 || n2) {
21
        if (n0) tmp = helper(2, n0 - 1, n1, n2, next_turn);
22
        if (tmp != turn && n2) tmp = helper(1, n0, n1, n2 - 1, next_turn);
23
      }
24
    }
25

26
    return tmp;
27
  }
28

29
  bool stoneGameIX(vector<int> &stones) {
30
    int n0 = 0, n1 = 0, n2 = 0;
31

32
    for (auto &x : stones) {
33
      int tmp = x % 3;
34
      if (tmp == 0)
35
        n0++;
36
      else if (tmp == 1)
37
        n1++;
38
    }
39

40
    n2 = stones.size() - n0 - n1;
41
    n0 = n0 % 2; // without this small line we will have TLE and whan I wrote
42
                 // contest I don't consider it =(
43
    return helper(0, n0, n1, n2, 0) == 0;
44
  }
45
};