2171C2.md (3839B)
1 Source: https://codeforces.com/problemset/problem/2171/C2 2 3 C2. Renako Amaori and XOR Game (hard version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Yup. I couldn't do this any longer. No. Freaking. Way. 22 23 — Renako Amaori 24 25 This is the hard version of the problem. The only difference between the easy and hard versions is that in the hard version, $a_i, b_i \leq 10^6$. 26 27 Renako is stuck between a rock and a hard place... and by that, of course, I mean Ajisai and Mai! Both of them want to hang out with her, and she just can't decide! So Ajisai and Mai have decided to play the XOR game. 28 29 Ajisai and Mai are given arrays $a$ and $b$ of length $n$ ($0\leq a_i, b_i\leq {\color{red}{10^6}}$). They will play a game that lasts for $n$ turns, where Ajisai moves on odd-numbered turns and Mai moves on even-numbered turns. On the $i$-th turn, the player to move may choose to swap $a_i$ and $b_i$, or pass. 30 31 Note that if a swap occurs, the index that is being swapped must match the turn number. For example, on the first turn, Ajisai may choose to swap $a_1$ and $b_1$, or pass. On the second turn, Mai may choose to swap $a_2$ and $b_2$, or pass. This continues for $n$ turns. Thus, only Ajisai can swap odd indices, and only Mai can swap even indices. 32 33 At the end of the game, Ajisai achieves a score of $a_1 \oplus a_2 \oplus \dots \oplus a_n$, and Mai achieves a score of $b_1 \oplus b_2 \oplus \dots \oplus b_n$$^{\text{∗}}$. The player with the higher score wins. If the players have the same score, the game ends in a tie. 34 35 Determine the outcome of the game with optimal play. More formally, one player is considered to win with optimal play if there exists a strategy for them such that they always win, regardless of their opponent's choices. The game is considered a tie with optimal play if neither player has such a strategy. 36 37 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) 38 39 Input 40 41 The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases. 42 43 The first line of each test case contains a single integer $n$ ($1\leq n\leq 2\cdot 10^5$). 44 45 The second line of each test case contains $n$ integers, $a_1, a_2, \dots, a_n$ ($0\leq a_i\leq 10^6$). 46 47 The third line of each test case contains $n$ integers, $b_1, b_2, \dots, b_n$ ($0\leq b_i\leq 10^6$). 48 49 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 50 51 Output 52 53 For each test case, output on a single line "Ajisai" if Ajisai wins with optimal play, "Mai" if Mai wins with optimal play, or "Tie" if the game ends in a tie with optimal play. 54 55 You may output the answer in any case (upper or lower). For example, the strings "mAi", "mai", "MAI", and "maI" will be recognized as "Mai". 56 57 Example 58 59 Input 60 61 ``` 62 6 63 64 4 65 66 1 4 6 1 67 68 3 2 3 7 69 70 6 71 72 20 11 1 7 7 0 73 74 14 8 3 6 17 6 75 76 4 77 78 2 6 3 6 79 80 3 4 7 1 81 82 5 83 84 1 4 5 5 3 85 86 6 7 1 2 13 87 88 6 89 90 9 5 9 17 17 6 91 92 1 13 6 13 1 15 93 94 5 95 96 2 3 8 1 5 97 98 3 1 6 14 7 99 ``` 100 101 Output 102 103 ``` 104 Mai 105 106 Ajisai 107 108 Tie 109 110 Ajisai 111 112 Mai 113 114 Tie 115 ``` 116 117 Note 118 119 In the first example, one way the game might play out is as follows: 120 121 On turn 1, Ajisai chooses to swap $a_1$ and $b_1$. Now the arrays are $a = [3, 4, 6, 1]$ and $b = [1, 2, 3, 7]$. 122 123 On turn 2, Mai chooses to swap $a_2$ and $b_2$. Now the arrays are $a = [3, 2, 6, 1]$ and $b = [1, 4, 3, 7]$. 124 125 On turn 3, Ajisai chooses to pass. 126 127 On turn 4, Mai chooses to swap $a_4$ and $b_4$. Now the arrays are $a = [3, 2, 6, 7]$ and $b = [1, 4, 3, 1]$. 128 129 Now, Ajisai's final score is $3\oplus 2\oplus 6\oplus 7 = 0$ and Mai's final score is $1\oplus 4\oplus 3\oplus 1 = 7$. Therefore, Mai wins the game. 130 131 It is not guaranteed that the above description is representative of optimal play. 132 133 For additional examples, see the examples of the easy version.