I JOI Co., Ltd.:s fabrik finns det $N$ bord, numrerade från $0$ till $N-1$. I fabriken finns det $N-1$ transportband, numrerade från $0$ till $N-2$. Transportband $i$ ($0 \le i \le N-2$) förbinder bord $A_i$ och bord $B_i$. Det transporterar produkter från det ena bordet till det andra bordet. Vi kan dock inte se transportriktningen. Om vi bortser från transportbandens riktningar är varje par av bord sammanbundna via ett antal transportband.

IOI-kun är fabrikschef. Eftersom han har glömt transportriktningen för varje transportband kommer han att utföra följande sekventiella operationer flera gånger.

1. Han väljer ett antal transportband och vänder på transportriktningen för de valda transportbanden.
2. Han väljer ett antal bord och placerar en produkt på varje valt bord.

3. För varje bord där en produkt har placerats inträffar något av följande samtidigt.

   • Om det inte finns något transportband som transporterar produkter från bordet händer ingenting.
   • Om det finns transportband som transporterar produkter från bordet transporteras produkten på bordet av ett sådant transportband. Produkten stannar vid transportbandets målbord. Produkten kommer inte att röra sig mer.

4. IOI-kun kontrollerar för varje bord om det finns en eller flera produkter på det. Om det finns produkter på ett bord tar IOI-kun bort dem alla.

5. För varje transportband vars riktning vändes i operation 1. återställer IOI-kun dess riktning. Dess riktning blir återigen den ursprungliga riktningen.

IOI-kun vill fastställa den ursprungliga riktningen för varje transportband genom att utföra de ovanstående sekventiella operationerna högst $30$ gånger.

Skriv ett program som, givet information om borden som förbinds av transportbanden, implementerar IOI-kuns strategi för att fastställa den ursprungliga riktningen för varje transportband genom att utföra de ovanstående sekventiella operationerna högst $30$ gånger.

Implementeringsdetaljer

Du ska skicka in en fil.

Filen heter conveyor.cpp. Den ska implementera följande funktion. Programmet ska inkludera conveyor.h med hjälp av preprocessordirektivet #include.

I conveyor.cpp ska följande funktion implementeras.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

  Denna funktion anropas endast en gång för varje testfall.

  • Parametern N är antalet bord $N$.
  • Parametrarna A, B är fält av längd $N-1$ som beskriver borden som förbinds av transportbanden.

  Ditt program kan anropa följande funktioner.

  • std::vector<int> Query(std::vector<int> x, std::vector<int> y)

    Med hjälp av denna funktion utför IOI-kun operationerna i fabriken.

    • Parametern x är ett fält av längd $N-1$. För $0 \le i \le N-2$ vänder IOI-kun på riktningen för transportband $i$ om x[i] = 1, och vänder inte på riktningen för transportband $i$ om x[i] = 0.
    • Parametern y är ett fält av längd $N$. För $0 \le j \le N-1$ placerar IOI-kun en produkt på bord $j$ om y[j] = 1, och placerar inte någon produkt på bord $j$ om y[j] = 0.
    • Låt z vara returvärdet från denna funktion. Det är ett fält av längd $N$. För $0 \le j \le N-1$ finns det en eller flera produkter på bord $j$ om z[j] = 1, och det finns ingen produkt på bord $j$ om z[j] = 0.
    • Längden på fältet x måste vara lika med $N-1$. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [1].
    • Varje element i fältet x måste vara 0 eller 1. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [2].
    • Längden på fältet y måste vara lika med $N$. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [3].
    • Varje element i fältet y måste vara 0 eller 1. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [4].
    • Funktionen Query får inte anropas mer än $30$ gånger. Om den anropas mer än $30$ gånger bedöms ditt program som Wrong Answer [5].

  • void Answer(std::vector<int> a)

    Med hjälp av denna funktion rapporterar IOI-kun den ursprungliga riktningen för varje transportband.

    • Parametern a är ett fält av längd $N-1$. För $0 \le i \le N-2$ transporterar transportband $i$ produkter från $A_i$ till $B_i$ om a[i] = 0, och det transporterar produkter från $B_i$ till $A_i$ om a[i] = 1.
    • Längden på fältet a måste vara lika med $N-1$. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [6].
    • Varje element i fältet a måste vara 0 eller 1. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [7].
    • Om IOI-kun rapporterar fel riktning för något transportband bedöms ditt program som Wrong Answer [8].
    • Funktionen Answer måste anropas exakt en gång. Om funktionen Answer anropas mer än en gång bedöms ditt program som Wrong Answer [9]. När funktionen Solve avslutas, om funktionen Answer inte har anropats, bedöms ditt program som Wrong Answer [10].

Viktiga anmärkningar

• Ditt program kan implementera andra funktioner för internt bruk eller använda globala variabler.
• Ditt program får inte använda standard inmatning (standard input) eller standard utmatning (standard output). Ditt program får inte kommunicera med andra filer på något sätt. Ditt program får dock skriva ut felsökningsinformation till standard felutmatning (standard error).

Kompilering och testkörning

Du kan ladda ner en arkivfil från tävlingens webbsida som innehåller exempelbedömaren (sample grader) för att testa ditt program. Arkivfilen innehåller också en exempelkällfil för ditt program.

Exempelbedömaren är filen grader.cpp. För att testa ditt program, lägg grader.cpp, conveyor.cpp och conveyor.h i samma katalog och kör följande kommando för att kompilera dina program. Alternativt kan du köra compile.sh som finns i arkivfilen.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

När kompileringen lyckas skapas den körbara filen grader.

Observera att den faktiska bedömaren skiljer sig från exempelbedömaren. Exempelbedömaren körs som en enda process som läser indata från standard inmatning och skriver resultaten till standard utmatning.

Indata för exempelbedömaren

Exempelbedömaren läser följande data från standard inmatning.

$$ \begin{array}{llll} N \\ A_0 & A_1 & \cdots & A_{N-2} \\ B_0 & B_1 & \cdots & B_{N-2} \\ C_0 & C_1 & \cdots & C_{N-2} \end{array} $$

För $0 \le i \le N-2$ gäller $C_i=0$ om transportband $i$ transporterar produkter från bord $A_i$ till bord $B_i$. Annars gäller $C_i=1$.

Utdata från exempelbedömaren

Exempelbedömaren skriver ut följande information till standard utmatning (citattecken för tydlighetens skull).

• Om ditt program bedöms som korrekt rapporterar den antalet funktionsanrop till Query som “Accepted: 22”.
• Om ditt program bedöms som någon typ av Wrong Answer skriver exempelbedömaren ut typen som “Wrong Answer [4]”.

Om ditt program uppfyller villkoren för flera typer av Wrong Answer rapporterar exempelbedömaren endast en av dem.

I exempelbedömaren väljs det transportband som transporterar produkten, bland de transportband som transporterar produkter från bordet där en produkt placerats, likformigt och slumpmässigt med hjälp av pseudoslumptal vars resultat inte ändras mellan olika körningar. För att ändra fröet (seed) för pseudoslumptalen, kör exempelbedömaren med ett heltalsargument enligt följande.

./grader 2023

Anmärkningar om bedömning

För vissa av testfallen är den faktiska bedömaren adaptiv. Detta innebär att bedömaren inte har ett fast svar från början, utan svarar utifrån tidigare funktionsanrop till Query. Det garanteras att det finns minst ett svar som inte motsäger något av bedömarens svar.

Begränsningar

All indata uppfyller följande villkor.

• $0 \le A_i \le N-1$ ($0 \le i \le N-2$).
• $0 \le B_i \le N-1$ ($0 \le i \le N-2$).
• Om vi bortser från transportbandens riktningar är varje par av bord sammanbundna via ett antal transportband.

Deluppgifter

1. (1 poäng) $N=2$.
2. (14 poäng) $N=30$.
3. (10 poäng) $N=100\,000$, $A_i=i$ ($0 \le i \le N-2$), $B_i=i+1$ ($0 \le i \le N-2$).
4. (75 poäng) $N=100\,000$.

Exempel på kommunikation

Här är ett exempel på indata för exempelbedömaren och motsvarande funktionsanrop.

Indata 1

3
0 2
2 1
1 0

Exempel på funktionsanrop

För det första funktionsanropet till Query är [0, 1, 0] ett annat möjligt returvärde utöver [1, 0, 0].

För det andra funktionsanropet till Query transporteras produkten på bord $0$ till bord $2$ genom att passera via transportband $0$, och stannar där. Observera att denna produkt inte kommer att transporteras vidare till bord $1$ genom att passera via transportband $1$.

Observera att detta indataexempel inte uppfyller begränsningarna för någon deluppgift.

Bland de filer som kan hämtas från tävlingens webbsida uppfyller sample-02.txt begränsningarna för Deluppgift $1$, och sample-03.txt uppfyller begränsningarna för Deluppgift $2$.