Stone game

#include <algorithm>
#include <iostream>
#include <map>


std::map<std::pair<int, int>, int> memo;

// 2 = win, 1 = draw, 0 = loss;

#define UPDATE(opponent_result) local_best = std::max(2 - opponent_result, local_best); if (local_best == 2) {memo[inkey] = 2; return 2;};

// this is actually horrible
int stone_game(int a, int b) {
  {
    int tmp = a;
    a = std::min(tmp, b);
    b = std::max(tmp, b);
  }
  const std::pair<int, int> inkey = {a, b};
  const auto it = memo.find(inkey);
  if (it != memo.end()) {
    return it->second;
  }
  memo[inkey] = 1;
  if (a == b) {
    memo[inkey] = 0;
    return 0;
  }
  if (a == 0 || b == 0) {
    memo[inkey] = 2;
    return 2;
  }

  int local_best = 0;
  for (int i = 1; i <= a; i++)
  {
    UPDATE(stone_game(a - i, b));
    UPDATE(stone_game(a - i, b + i));
    UPDATE(stone_game(a, b - i));
    UPDATE(stone_game(a + i, b - i));
  }
  for (int i = a + 1; i <= b; i++)
  {
    UPDATE(stone_game(a, b - i));
    UPDATE(stone_game(a + i, b - i));
  }
  memo[inkey] = local_best;
  return local_best;
}

int main() {
  int a, b;
  std::cin >> a;
  std::cin >> b;
  // can take any n of stones from either pile and either move them onto other
  // pile or discard. first player that cannot make moves (i.e., both piles
  // empty) loses winner is one whose move empties the last pile alternatively,
  // lose the game if you empty the first pile from below, also seen that winner
  // is one who gets pile to 1 1 unsure how this could ever be a draw

  // 1 2
  // uolevi can make it 1 1 or 2 1; 2 1 -> 1 2 will go on forever, so 1 1
  // 1 1
  // maija will always empty one pile
  // 0 1 or 1 0, and then uolevi can discard the last stone -> win

  // starting at 1 1 -> as if maija got it to 1 1 -> maija wins
  // starting at 2 2 -> zeroing = loss for uolevi
  // -> making either one 1 = loss for uolevi because maija can then force 1 1
  // -> 0 1 -> 0 0

  // win if your move makes a and b equal

  // starting at 1 n -> uolevi can make 1 1 -> win
  // starting at m n -> (m-1), (n-1)

  // 3 3 
  // 1 3, 1 5, 2 3, 2 4
  int result = stone_game(a,b);
  switch (result)
  {
    case 0:
        std::cout << "Maija";
        break;
    case 1:
        std::cout << "Draw";
        break;
    case 2:
        std::cout << "Uolevi";
        break;
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: TIME LIMIT EXCEEDED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: TIME LIMIT EXCEEDED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: TIME LIMIT EXCEEDED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: TIME LIMIT EXCEEDED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED