Fruit game

#include <iostream>
#include <vector>

int main() {
	// say the sequence starts and ends with banana or apple, then banana or apple loses. Otherwise, the one whose side depletes first wins. It is always optimal to take from your own side if possible
	int t;
	std::cin >> t;
	for (int j = 0; j < t; ++j) {
		std::string seq;
		std::cin >> seq;
		int n = seq.size();
		std::vector<int> left;
		std::vector<int> right;
		int left_owner = (seq[0] == 'C' ? 0 : (seq[0] == 'A' ? 1 : -1));
		int right_owner = (seq[n-1] == 'C' ? 0 : (seq[n-1] == 'A' ? 1 : -1));
		int winner = 0;
		//std::cout << left_owner << ' ' << right_owner << '\n';
		for (int i = 0; i < n; ++i) {
			if (seq[i] == 'C') break;
			if (seq[i] == 'A') {
				left.push_back(1);
			} else {
				left.push_back(-1);
			}
		}
		for (int i = n-1; i >= 0; --i) {
			if (seq[i] == 'C') break;
			if (seq[i] == 'A') {
				right.push_back(1);
			} else {
				right.push_back(-1);
			}
		}
		if ((left_owner == 0) || (right_owner == 0)) {
			if (left_owner == 0) winner = -right_owner;
			if (right_owner == 0) winner = -left_owner;
		} else {
			if (left_owner == right_owner) {
				winner = - left_owner;
			} else {
				int turn = 1;
				while((!left.empty()) && (!right.empty())) {
					if (left_owner == turn) {
						if (left.back() == turn) {
							left.pop_back();
						} else if (right.back() == turn) {
							right.pop_back();
						}
					} else {
						if (right.back() == turn) {
							right.pop_back();
						} else if (left.back() == turn) {
							left.pop_back();
						}
					}
					turn = -turn;
				}
				winner = (left.empty() ? left_owner : right_owner);
			}
		}
		std::cout << (winner == 1 ? "Uolevi" : "Maija") << '\n';
	}
}

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: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

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: ACCEPTED

Test 56

Verdict: ACCEPTED