Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100
Estadísticas

Tohtori Menji on tekoälyasiantuntija. Nyt hän kouluttaa Botia, joka on AGI (Artificial Game Intelligence).

Opettaakseen Botia pelaamaan pelejä hän pelaa Botin kanssa joka päivä. Tänään he pelaavat seuraavaa peliä:

Peli alkaa jonolla, jossa on $2n$ ei-negatiivista kokonaislukua, $a_1, a_2, \cdots, a_{2n}$, sekä luvulla $S$. Aluksi $S = 0$.

Menji ja Bot toimivat vuorotellen; Menji aloittaa:

  • Menjin vuorolla hän valitsee jonosta luvun $x$, asettaa $S \leftarrow S \oplus x$ ja poistaa luvun $x$ jonosta. Huomaa, että $\oplus$ on bittikohtainen XOR-funktio (poissulkeva tai).
  • Botin vuorolla hän valitsee jonosta luvun $x$ ja poistaa luvun $x$ jonosta.

Peli päättyy, kun jonossa ei ole enää yhtään lukua jäljellä. Menji voittaa jos ja vain jos lopussa $S = 0$; muussa tapauksessa Bot voittaa.

Menji pohtii, kumpi voittaa pelin, jos molemmat pelaajat pelaavat optimaalisesti.

Syöte

Syöte sisältää useita testitapauksia. Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka on kuvattu tehtävänannossa.

Toinen rivi sisältää $2n$ kokonaislukua $a_1, a_2, \cdots, a_{2n}$ ($0 \le a_i < 2^{30}$), jotka kuvaavat pelin kokonaislukuja.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden omalle rivilleen Menji, jos Menji voi voittaa pelin; muussa tapauksessa tulosta omalle rivilleen Bot.

Esimerkki

5
2
1 1 3 3
2
1 1 1 3
3
1 1 4 5 1 4
3
1 9 1 9 8 10
6
1 1 4 5 1 4 1 9 1 9 8 10
Bot
Menji
Menji
Menji
Bot

Huomautus

Ensimmäisessä testitapauksessa riippumatta siitä, minkä luvun Menji valitsee, Bot voi aina valita saman luvun, joten Menji valitsee aina yhden luvun $1$ ja yhden luvun $3$, jolloin $S = 1 \oplus 3 = 2 \neq 0$, joten Bot voi aina voittaa.

Toisessa testitapauksessa Menji voi valita luvun $1$ ensimmäisellä vuorolla; riippumatta siitä, mitä Bot valitsee, Menji voi valita toisen luvun $1$, joten Menji saa aina kaksi lukua $1$, jolloin $S = 1 \oplus 1 = 0$, joten Menji voi aina voittaa.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.