I fabrikken til JOI Co., Ltd. er det $N$ bord, nummerert fra $0$ til $N-1$. I fabrikken er det $N-1$ transportbånd, nummerert fra $0$ til $N-2$. Transportbånd $i$ ($0 \le i \le N-2$) forbinder bord $A_i$ og bord $B_i$. Det transporterer produkter fra det ene bordet til det andre bordet. Vi kan imidlertid ikke se transportretningen. Hvis vi ser bort fra retningene til transportbåndene, er hvert par av bord forbundet via et antall transportbånd.

IOI-kun er fabrikksjef. Siden han har glemt transportretningen til hvert transportbånd, vil han utføre følgende sekvensielle operasjoner flere ganger.

1. Han velger et antall transportbånd og snur transportretningen til de valgte transportbåndene.
2. Han velger et antall bord og legger et produkt på hvert valgt bord.

3. For hvert bord der det er lagt et produkt, skjer ett av følgende samtidig.

   • Hvis det ikke er noe transportbånd som transporterer produkter fra bordet, skjer ingenting.
   • Hvis det finnes transportbånd som transporterer produkter fra bordet, blir produktet på bordet transportert av ett slikt transportbånd. Produktet stopper ved destinasjonen til transportbåndet. Produktet vil ikke bevege seg mer.

4. IOI-kun sjekker for hvert bord om det er ett eller flere produkter på det. Hvis det er produkter på et bord, tar IOI-kun bort alle sammen.

5. For hvert transportbånd hvis retning ble snudd i operasjon 1., tilbakestiller IOI-kun retningen. Retningen blir igjen den opprinnelige retningen.

IOI-kun ønsker å fastslå den opprinnelige retningen til hvert transportbånd ved å utføre de ovennevnte sekvensielle operasjonene høyst $30$ ganger.

Skriv et program som, gitt informasjon om bordene som er forbundet av transportbåndene, implementerer IOI-kuns strategi for å fastslå den opprinnelige retningen til hvert transportbånd ved å utføre de ovennevnte sekvensielle operasjonene høyst $30$ ganger.

Implementasjonsdetaljer

Du må sende inn én fil.

Filen heter conveyor.cpp. Den skal implementere følgende funksjon. Programmet skal inkludere conveyor.h ved hjelp av preprosessordirektivet #include.

I conveyor.cpp skal følgende funksjon implementeres.

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

  Denne funksjonen kalles kun én gang for hvert testtilfelle.

  • Parameteren N er antallet bord $N$.
  • Parameterne A, B er tabeller med lengde $N-1$, som beskriver bordene som er forbundet av transportbåndene.

  Programmet ditt kan kalle følgende funksjoner.

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

    Ved hjelp av denne funksjonen utfører IOI-kun operasjonene i fabrikken.

    • Parameteren x er en tabell med lengde $N-1$. For $0 \le i \le N-2$ snur IOI-kun retningen til transportbånd $i$ hvis x[i] = 1, og snur ikke retningen til transportbånd $i$ hvis x[i] = 0.
    • Parameteren y er en tabell med lengde $N$. For $0 \le j \le N-1$ legger IOI-kun et produkt på bord $j$ hvis y[j] = 1, og legger ikke et produkt på bord $j$ hvis y[j] = 0.
    • La z være returverdien fra denne funksjonen. Det er en tabell med lengde $N$. For $0 \le j \le N-1$ er det ett eller flere produkter på bord $j$ hvis z[j] = 1, og det er ingen produkter på bord $j$ hvis z[j] = 0.
    • Lengden på tabellen x må være lik $N-1$. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [1].
    • Hvert element i tabellen x må være 0 eller 1. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [2].
    • Lengden på tabellen y må være lik $N$. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [3].
    • Hvert element i tabellen y må være 0 eller 1. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [4].
    • Funksjonen Query må ikke kalles mer enn $30$ ganger. Hvis den kalles mer enn $30$ ganger, blir programmet ditt bedømt som Wrong Answer [5].

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

    Ved hjelp av denne funksjonen rapporterer IOI-kun den opprinnelige retningen til hvert transportbånd.

    • Parameteren a er en tabell med lengde $N-1$. For $0 \le i \le N-2$ transporterer transportbånd $i$ produkter fra $A_i$ til $B_i$ hvis a[i] = 0, og det transporterer produkter fra $B_i$ til $A_i$ hvis a[i] = 1.
    • Lengden på tabellen a må være lik $N-1$. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [6].
    • Hvert element i tabellen a må være 0 eller 1. Hvis denne betingelsen ikke er oppfylt, blir programmet ditt bedømt som Wrong Answer [7].
    • Hvis IOI-kun rapporterer feil retning for et transportbånd, blir programmet ditt bedømt som Wrong Answer [8].
    • Funksjonen Answer må kalles nøyaktig én gang. Hvis funksjonen Answer kalles mer enn én gang, blir programmet ditt bedømt som Wrong Answer [9]. Når funksjonen Solve avsluttes, hvis funksjonen Answer ikke er blitt kalt, blir programmet ditt bedømt som Wrong Answer [10].

Viktige merknader

• Programmet ditt kan implementere andre funksjoner for internt bruk, eller bruke globale variabler.
• Programmet ditt må ikke bruke standard inndata (standard input) eller standard utdata (standard output). Programmet ditt må ikke kommunisere med andre filer på noen måte. Programmet ditt kan imidlertid skrive ut feilsøkingsinformasjon til standard feilutdata (standard error).

Kompilering og testkjøring

Du kan laste ned en arkivfil fra konkurransens nettside som inneholder eksempelbedømmeren (sample grader) for å teste programmet ditt. Arkivfilen inneholder også en eksempelkildefil for programmet ditt.

Eksempelbedømmeren er filen grader.cpp. For å teste programmet ditt, legg grader.cpp, conveyor.cpp og conveyor.h i samme mappe, og kjør følgende kommando for å kompilere programmene dine. Alternativt kan du kjøre compile.sh som ligger i arkivfilen.

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

Når kompileringen lykkes, genereres den kjørbare filen grader.

Merk at den faktiske bedømmeren er forskjellig fra eksempelbedømmeren. Eksempelbedømmeren vil bli kjørt som én enkelt prosess, som leser inndata fra standard inndata og skriver resultatene til standard utdata.

Inndata for eksempelbedømmeren

Eksempelbedømmeren leser følgende data fra standard inndata.

$$ \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} $$

For $0 \le i \le N-2$ har vi $C_i=0$ hvis transportbånd $i$ transporterer produkter fra bord $A_i$ til bord $B_i$. Ellers har vi $C_i=1$.

Utdata fra eksempelbedømmeren

Eksempelbedømmeren skriver ut følgende informasjon til standard utdata (anførselstegn for tydelighetens skyld).

• Hvis programmet ditt blir bedømt som riktig, rapporterer den antallet funksjonskall til Query som “Accepted: 22”.
• Hvis programmet ditt blir bedømt som en hvilken som helst type Wrong Answer, skriver eksempelbedømmeren ut typen som “Wrong Answer [4]”.

Hvis programmet ditt oppfyller betingelsene for flere typer Wrong Answer, rapporterer eksempelbedømmeren bare én av dem.

I eksempelbedømmeren blir det transportbåndet som transporterer produktet, blant transportbåndene som transporterer produkter fra bordet der et produkt er lagt, valgt uniformt og tilfeldig ved hjelp av pseudotilfeldige tall hvis resultater ikke endrer seg mellom ulike kjøringer. For å endre frøet (seed) til de pseudotilfeldige tallene, kjør eksempelbedømmeren med det første heltallsargumentet som følger.

./grader 2023

Merknader om bedømming

For noen av testtilfellene er den faktiske bedømmeren adaptiv. Dette betyr at bedømmeren ikke har et fast svar i starten, men svarer basert på tidligere funksjonskall til Query. Det er garantert at det finnes minst ett svar som ikke motsier noen av svarene fra bedømmeren.

Begrensninger

Alle inndata oppfyller følgende betingelser.

• $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$).
• Hvis vi ser bort fra retningene til transportbåndene, er hvert par av bord forbundet via et antall transportbånd.

Deloppgaver

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

Eksempel på kommunikasjon

Her er et eksempel på inndata for eksempelbedømmeren og tilhørende funksjonskall.

Inndata 1

3
0 2
2 1
1 0

Eksempel på funksjonskall

For det første funksjonskallet til Query er en annen mulig returverdi [0, 1, 0] i tillegg til [1, 0, 0].

For det andre funksjonskallet til Query blir produktet på bord $0$ transportert til bord $2$ ved å passere gjennom transportbånd $0$, og stopper der. Merk at dette produktet ikke vil bli transportert videre til bord $1$ ved å passere gjennom transportbånd $1$.

Merk at dette inndataeksempelet ikke oppfyller begrensningene til noen deloppgave.

Blant filene som kan hentes fra konkurransens nettside, oppfyller sample-02.txt begrensningene til Deloppgave $1$, og sample-03.txt oppfyller begrensningene til Deloppgave $2$.