Problem C
Maskroskaos

Innan Gösta dog av ålderdom kom vetenskapsmän på hur man kan göra människor odödliga. Hur detta gick till lämnas som en kluring för läsaren. Gösta har en äng med maskrosor. Efter lång väntan är den äntligen fullvuxen, och han kan nu skapa maskrosläsk med maskrosorna (se Maskrosor). Intressant nog är alla maskrosor inte riktigt samma: han har kommit fram till att det finns $N$ olika arter av maskrosor i hans äng. Han vill nu självklart veta om vissa maskrosarter skapar godare läsk än andra. Efter en del möda har Gösta lyckats plocka exakt $2$ stycken maskrosor av varje art. Precis när han skulle börja analysera de, så råkar han snubbla och blanda ihop alla maskrosor. Katastrof!

Eftersom maskrosorna är väldigt lika visuellt kommer han behöva använda sin pollen-analys-maskin. Denna fungerar genom att låta alla maskrosor i den blomma, och kan sedan analysera pollenet. Den kan då avgöra antalet unika arter maskrosor som finns i den. Den kan tyvärr inte avgöra om det finns en eller två av en viss art, eftersom mängden pollen kan variera väldigt mycket från maskros till maskros. Han har numrerat alla sina maskrosor från $1$ till $2N$.

Det finns två sätt som du kan använda maskinen på:

• Lägga in en maskros i maskinen.

• Ta ut en maskros ur maskinen (som redan finns i den).

Efter att du lägger in eller tar ut en maskros ur maskinen får du direkt reda på antalet unika arter maskrosor som finns i den. Gösta vill nu ha din hjälp att använda maskinen för att hitta vilka par av maskrosor som är av samma art. Eftersom han är odödlig har han inte bråttom, men vill ändå bli färdig inom "rimlig" tid. Därför kan han acceptera att du använder den som mest en miljon ($10^6$) gånger.

Implementation

Din lösning till problemet måste vara skriven i C++. Den ska inkludera filen maskroskaos.h. Du ska inte skapa en main-funktion. Istället ska du implementera funktionen

• void Solve(int N)
  Denna funktion kallas en gång för varje testfall, och funkar som ditt programs main-funktion.

  • Parametern $N$ ($1 \leq N \leq 43000$) är antalet arter av maskrosor som Gösta plockat.

  Ditt program kan använda följande funktioner för att lösa problemet.

  • int Query(int x)
    Där $x$ ($1 \leq X \leq 2N$) är indexet av en de $2N$ maskrosorna. Om $x$ inte finns i maskinen läggs den in. Om $x$ redan finns i maskinen tas den ut. Dess returvärde är antalet unika arter av maskrosor i maskinen efter att $x$ lagts in eller tagits ut. Om du anropar denna funktion mer än $10^6$ gånger eller anger ett $x$ som inte tillfredställer $1 \leq x \leq 2N$ får du Wrong Answer.

  • int Answer(int a, int b)
    När du anropar denna funktionen hävdar du att maskrosorna med index $a$ och $b$ är av samma art. Om du gör något av följande får du Wrong Answer.

    • Om Answer anropas med samma maskros mer än en gång. Exempelvis kommer anropet Answer(1,2) följt av Answer(1,3) ge Wrong Answer eftersom $1$ finns i båda.

    • $1 \leq a,b \leq 2N$ inte tillfredställs.

    • Maskrosorna med index $a$ och $b$ är av olika art.

    • Returnerar från Solve och du har inte anropat Answer exakt $N$ gånger.

Notera: funktionerna Query och Answer ska kallas på i funktionen Solve. (Se exempelkoden i maskroskaos.cpp)

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Testning av lösning

För att underlätta testningen av ditt program tillhandahåller vi ett exempelprogram och en exempeldomare. Dessa kan laddas ned vid attachments längst ned på sidan.

För att testa programmet kan du köra följande kommando:

• g++ -o grader grader.cpp maskroskaos.cpp

Detta kommer skapa filen grader, som du sedan kör för att testa programmet. Notera att denna exempeldomare skiljer sig från domaren som används för uppgiften. Det är dock garanterat att den riktiga domaren inte är adaptiv. Detta innebär att svaret bestäms innan ditt program körs, och den kan inte ändra svaret under körningens gång. Ditt program får inte skriva eller läsa från standard input/output (det vill säga, skriva och läsa från terminalen). Om du gör detta kommer du troligtvis få förvirrande fel.

Indataformat för exempeldomaren

Exempeldomaren läser indata på följande format:

• En rad med heltalet $N$.

• $N$ rader som vardera innehåller heltalen $a$ och $b$ ($1 \leq a,b \leq 2N$). Detta innebär att maskrosorna med index $a$ och $b$ är av samma art.

Utdataformat för exempeldomaren

Om ditt program klarade testfallet skriver den ut "Accepted. Queries: $q$", där $q$ är antalet gånger ditt program anropade Query.

Om ditt program är inkorrekt skriver den ut "WA. $e$", där $e$ är felet ditt program gjorde. Om ditt program har flera fel kommer den bara skriva ut det första felet den gör.

Exempel-interaktion

Betrakta följande indata till domaren:

3
1 5
2 4
3 6

En giltig interaktion som löser problem kan se ut som följande: