Anna och Bruno är spelmästare. De ska spela ett spel med D-taro som är spelets givare.

I detta spel befinner sig Anna och Bruno i olika rum. De kan endast kommunicera med varandra med hjälp av en trasig apparat. D-taro ger ett heltal till Anna. För Anna och Bruno är syftet med detta spel att skicka det givna heltalet från Anna till Bruno med hjälp av apparaten.

När spelet startar deklarerar Anna i början ett heltal $m$ mellan $1$ och $2\,000$, inklusive. Därefter spelar de $Q$ rundor. Runda $i$ ($1\le i\le Q$) genomförs enligt följande.

1. D-taro ger ett heltal $A_i$ till Anna.
2. Anna matar in fälten $s_i,t_i$ i apparaten. Varje element i fälten $s_i,t_i$ ska vara antingen $0$ eller $1$. Fälten $s_i,t_i$ ska ha samma längd, och längden är mellan $1$ och $m$, inklusive.
3. Låt $u_i$ vara ett fält som erhållits från fälten $s_i$ och $t_i$ genom riffelblandning (riffle shuffle, se nedan). Därefter skickar apparaten $u_i$ till Bruno.
4. Bruno skickar ett heltal till D-taro. Om detta heltal är detsamma som heltalet $A_i$ som D-taro gav till Anna, vinner Anna och Bruno denna runda.

Skriv program som implementerar Annas och Brunos strategier så att de vinner alla de $Q$ rundorna.

Riffelblandning

Vi säger att ett fält $Z$ erhålls från fälten $X$ och $Y$ genom riffelblandning om vi kan dela in elementen i fältet $Z$ i två grupper så att följande två villkor är uppfyllda.

• Fältet som består av elementen i den första gruppen i samma ordning är lika med fältet $X$.
• Fältet som består av elementen i den andra gruppen i samma ordning är lika med fältet $Y$.

Till exempel erhålls fältet $Z=[1,1,1,0,0,0]$ från $X=[1,1,0]$ och $Y=[1,0,0]$ genom riffelblandning eftersom fältet som består av det första, andra och fjärde elementet i $Z$ i samma ordning är fältet $[1,1,0]$, och fältet som består av det tredje, femte och sjätte elementet i $Z$ i samma ordning är fältet $[1,0,0]$.

Å andra sidan, om $X=[1,1,0]$, $Y=[1,0,0]$ och $Z=[0,0,0,1,1,1]$, är fältet $Z$ inte erhållet från $X$ och $Y$ genom riffelblandning.

Implementeringsdetaljer

Du måste skicka in två filer.

Den första filen är Anna.cpp. Den ska implementera Annas strategi. Den ska implementera följande funktioner. Programmet ska inkludera Anna.h med hjälp av preprocessordirektivet #include.

• int Declare()

  Denna funktion anropas en gång i början.

  • Returvärdet är heltalet $m$ som deklareras av Anna.
  • Heltalet $m$ ska vara mellan $1$ och $2\,000$, inklusive. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Efter att funktionen Declare har anropats, anropas denna funktion $Q$ gånger. Det $i$:te anropet ($1\le i\le Q$) till denna funktion motsvarar Steg 1 och Steg 2 för runda $i$.

  • Parametern A är heltalet $A_i$ som D-taro gav till Anna.
  • Returvärdet är paret av de två fälten $s_i,t_i$ som Anna matar in i apparaten.
  • Varje element i fälten $s_i,t_i$ ska vara antingen $0$ eller $1$. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [2].
  • Båda längderna på fälten $s_i,t_i$ ska vara mellan $1$ och $m$, inklusive. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [3].
  • Fälten $s_i,t_i$ ska ha samma längd. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [4].

Den andra filen är Bruno.cpp. Den ska implementera Brunos strategi. Den ska implementera följande funktion. Programmet ska inkludera Bruno.h med hjälp av preprocessordirektivet #include.

• long long Bruno(std::vector<int> u)

  Efter att Anna har matat in fälten i apparaten anropas denna funktion en gång. Totalt anropas denna funktion $Q$ gånger. Det $i$:te anropet ($1\le i\le Q$) till denna funktion motsvarar Steg 3 och Steg 4 för runda $i$.

  • Parametern u är fältet $u_i$ som skickas av apparaten till Bruno för runda $i$.
  • Returvärdet är heltalet som skickas av Bruno till D-taro.
  • Returvärdet ska vara detsamma som heltalet $A_i$ som D-taro gav till Anna. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [5].

Viktiga anmärkningar

• Ditt program kan implementera andra funktioner för internt bruk, eller använda globala variabler. Inskickade filer kommer att kompileras med gradern och bli en enda körbar fil. Alla globala variabler och interna funktioner bör deklareras i en namnlös namnrymd (unnamed namespace) för att undvika konflikter med andra filer. Vid bedömningen kommer det att köras som två processer för Anna och Bruno. Annas process och Brunos process kan inte dela globala variabler.
• Ditt program får inte använda standardindata eller standardutdata. Ditt program får inte kommunicera med andra filer på något sätt. Ditt program får dock skriva ut felsökningsinformation till standardfelutdata (standard error).

Kompilering och testkörning

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

Exempelgradern är filen grader.cpp. För att testa ditt program, lägg grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h i samma katalog och kör följande kommando för att kompilera dina program.

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

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

Observera att den faktiska gradern skiljer sig från exempelgradern. Exempelgradern kommer att köras som en enda process, som läser indata från standardindata och skriver resultaten till standardutdata.

Indata för exempelgradern

Exempelgradern läser följande data från standardindata.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Utdata från exempelgradern

Exempelgradern skriver ut följande information till standardutdata (citattecken för tydlighetens skull).

• Om ditt program bedöms som korrekt skriver den ut returvärdet $m$ från funktionen Declare som “Accepted: 2000”.
• Om ditt program bedöms som något av Wrong Answer skriver exempelgradern ut dess typ som “Wrong Answer [1]”.

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

När exempelgradern körs beräknas riffelblandningen för varje runda med hjälp av pseudoslumptal. Deras resultat ändras inte mellan körningar. För att ändra fröet (seed) för pseudoslumptalen, kör exempelgradern på följande sätt.

./grader 2022

Det första argumentet ska vara ett heltal.

Begränsningar

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Deluppgifter

1. (5 poäng) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 poäng) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 poäng) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 poäng) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 poäng) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 poäng) Inga ytterligare begränsningar. För denna deluppgift beräknas din poäng enligt följande.

   • Låt $m^*$ vara maximum av de heltal $m$ som deklareras av Anna för alla testfall i denna deluppgift.
   • Din poäng är som följer.

Exempel

Här är ett exempelindata för exempelgradern och motsvarande funktionsanrop.

Indata 1

2
42
2000

Exempel på funktionsanrop

I detta exempelindata finns det $Q\ (=2)$ rundor. För runda 1 ger D-taro heltalet $A_1\ (=42)$ till Anna. För runda 2 ger D-taro heltalet $A_2\ (=2000)$ till Anna.

Detta exempelindata uppfyller begränsningarna för alla deluppgifter.