codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.