Í verksmiðju JOI Co., Ltd. eru $N$ borð, númeruð frá $0$ til $N-1$. Í verksmiðjunni eru $N-1$ færibönd, númeruð frá $0$ til $N-2$. Færiband $i$ ($0 \le i \le N-2$) tengir borð $A_i$ og borð $B_i$. Það flytur vörur frá öðru borðinu til hins. Hins vegar getum við ekki séð flutningsstefnuna. Ef við lítum fram hjá stefnum færibandanna er hvert par af borðum tengt saman með nokkrum færiböndum.

IOI-kun er verksmiðjustjórinn. Þar sem hann hefur gleymt flutningsstefnu hvers færibands mun hann framkvæma eftirfarandi röð aðgerða nokkrum sinnum.

1. Hann velur nokkur færibönd og snýr við flutningsstefnu völdu færibandanna.
2. Hann velur nokkur borð og setur vöru á hvert valið borð.

3. Fyrir hvert borð þar sem vara er sett gerist annað hvort af eftirfarandi samtímis.

   • Ef ekkert færiband flytur vörur frá því gerist ekkert.
   • Ef það eru færibönd sem flytja vörur frá því er varan á borðinu flutt með einu slíku færibandi. Varan stöðvast á áfangastað færibandsins. Varan mun ekki hreyfast meira.

4. IOI-kun athugar fyrir hvert borð hvort ein eða fleiri vörur séu á því. Ef það eru vörur á borði tekur IOI-kun þær allar.

5. Fyrir hvert færiband sem snúið var við í aðgerð 1. breytir IOI-kun stefnu þess til baka. Stefna þess verður aftur upphaflega stefnan.

IOI-kun vill ákvarða upphaflega stefnu hvers færibands með því að framkvæma ofangreinda röð aðgerða í mesta lagi $30$ sinnum.

Skrifið forrit sem, miðað við upplýsingar um borðin sem færiböndin tengja, útfærir áætlun IOI-kun til að ákvarða upphaflega stefnu hvers færibands með því að framkvæma ofangreinda röð aðgerða í mesta lagi $30$ sinnum.

Útfærsluatriði

Þú þarft að skila einni skrá.

Skráin heitir conveyor.cpp. Hún ætti að útfæra eftirfarandi fall. Forritið ætti að bæta við conveyor.h með forvinnsluskipuninni #include.

Í conveyor.cpp ætti að útfæra eftirfarandi fall.

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

  Þetta fall er aðeins kallað einu sinni fyrir hvert prófunartilvik.

  • Stikinn N er fjöldi borða $N$.
  • Stikarnir A, B eru fylki af lengd $N-1$, sem lýsa borðunum sem færiböndin tengja.

  Forritið þitt getur kallað á eftirfarandi föll.

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

    Með því að nota þetta fall framkvæmir IOI-kun aðgerðirnar í verksmiðjunni.

    • Stikinn x er fylki af lengd $N-1$. Fyrir $0 \le i \le N-2$ snýr IOI-kun við stefnu færibands $i$ ef x[i] = 1, og snýr ekki við stefnu færibands $i$ ef x[i] = 0.
    • Stikinn y er fylki af lengd $N$. Fyrir $0 \le j \le N-1$ setur IOI-kun vöru á borð $j$ ef y[j] = 1, og setur ekki vöru á borð $j$ ef y[j] = 0.
    • Látum z vera skilagildi þessa falls. Það er fylki af lengd $N$. Fyrir $0 \le j \le N-1$ eru ein eða fleiri vörur á borði $j$ ef z[j] = 1, og engin vara er á borði $j$ ef z[j] = 0.
    • Lengd fylkisins x ætti að vera jöfn $N-1$. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [1].
    • Hvert stak í fylkinu x ætti að vera 0 eða 1. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [2].
    • Lengd fylkisins y ætti að vera jöfn $N$. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [3].
    • Hvert stak í fylkinu y ætti að vera 0 eða 1. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [4].
    • Ekki má kalla á fallið Query oftar en $30$ sinnum. Ef kallað er á það oftar en $30$ sinnum er forritið þitt dæmt sem Wrong Answer [5].

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

    Með því að nota þetta fall tilkynnir IOI-kun upphaflega stefnu hvers færibands.

    • Stikinn a er fylki af lengd $N-1$. Fyrir $0 \le i \le N-2$ flytur færiband $i$ vörur frá $A_i$ til $B_i$ ef a[i] = 0, og það flytur vörur frá $B_i$ til $A_i$ ef a[i] = 1.
    • Lengd fylkisins a ætti að vera jöfn $N-1$. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [6].
    • Hvert stak í fylkinu a ætti að vera 0 eða 1. Ef þetta skilyrði er ekki uppfyllt er forritið þitt dæmt sem Wrong Answer [7].
    • Ef IOI-kun tilkynnir ranga stefnu færibands er forritið þitt dæmt sem Wrong Answer [8].
    • Kalla verður á fallið Answer nákvæmlega einu sinni. Ef kallað er á fallið Answer oftar en einu sinni er forritið þitt dæmt sem Wrong Answer [9]. Þegar fallinu Solve lýkur, ef ekki hefur verið kallað á fallið Answer, er forritið þitt dæmt sem Wrong Answer [10].

Mikilvægar athugasemdir

• Forritið þitt getur útfært önnur föll til innri nota, eða notað víðværar breytur.
• Forritið þitt má ekki nota staðalinntak né staðalúttak. Forritið þitt má ekki eiga samskipti við aðrar skrár með neinum hætti. Hins vegar má forritið þitt skrifa aflúsunarupplýsingar á staðalvilluúttak (standard error).

Þýðing og prófunarkeyrsla

Þú getur sótt safnskrá af vefsíðu keppninnar sem inniheldur sýnisyfirfarara (sample grader) til að prófa forritið þitt. Safnskráin inniheldur einnig sýniskóðaskrá fyrir forritið þitt.

Sýnisyfirfararinn er skráin grader.cpp. Til að prófa forritið þitt skaltu setja grader.cpp, conveyor.cpp, conveyor.h í sömu möppu og keyra eftirfarandi skipun til að þýða forritin þín. Einnig getur þú keyrt compile.sh sem er í safnskránni.

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

Þegar þýðingin tekst verður keyrsluskráin grader búin til.

Athugið að raunverulegi yfirfararinn er ólíkur sýnisyfirfararanum. Sýnisyfirfararinn verður keyrður sem eitt ferli sem les inntaksgögn af staðalinntaki og skrifar niðurstöðurnar á staðalúttak.

Inntak fyrir sýnisyfirfararann

Sýnisyfirfararinn les eftirfarandi gögn af staðalinntaki.

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

Fyrir $0 \le i \le N-2$ höfum við $C_i=0$ ef færiband $i$ flytur vörur frá borði $A_i$ til borðs $B_i$. Annars höfum við $C_i=1$.

Úttak sýnisyfirfararans

Sýnisyfirfararinn skrifar eftirfarandi upplýsingar á staðalúttak (gæsalappir eru til skýringar).

• Ef forritið þitt er dæmt rétt tilkynnir hann fjölda fallakalla á Query sem „Accepted: 22“.
• Ef forritið þitt er dæmt sem einhver tegund af Wrong Answer skrifar sýnisyfirfararinn tegundina sem „Wrong Answer [4]“.

Ef forritið þitt uppfyllir skilyrði nokkurra tegunda af Wrong Answer tilkynnir sýnisyfirfararinn aðeins eina þeirra.

Í sýnisyfirfararanum er færibandið sem flytur vöruna, úr hópi þeirra færibanda sem flytja vörur frá borðinu þar sem vara er sett, valið jafndreift og af handahófi með gervihandahófskenndum tölum (pseudorandom numbers) þar sem niðurstöðurnar breytast ekki milli mismunandi keyrslna. Til að breyta fræi (seed) gervihandahófskenndu talnanna skaltu keyra sýnisyfirfararann með fyrsta heiltöluviðfanginu sem hér segir.

./grader 2023

Athugasemdir um yfirferð

Fyrir sum prófunartilvikin er raunverulegi yfirfararinn aðlögunarhæfur (adaptive). Þetta þýðir að yfirfararinn hefur ekki fast svar í upphafi, heldur svarar í samræmi við fyrri fallaköll á Query. Það er tryggt að til sé að minnsta kosti eitt svar sem stangast ekki á við nein svör yfirfararans.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

• $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$).
• Ef við lítum fram hjá stefnum færibandanna er hvert par af borðum tengt saman með nokkrum færiböndum.

Undirverkefni

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

Dæmi um samskipti

Hér er sýnisinntak fyrir sýnisyfirfararann og samsvarandi fallaköll.

Inntak 1

3
0 2
2 1
1 0

Dæmi um fallaköll

Fyrir fyrsta fallakallið á Query er annað mögulegt skilagildi [0, 1, 0] fyrir utan [1, 0, 0].

Fyrir annað fallakallið á Query er varan á borði $0$ flutt á borð $2$ með því að fara um færiband $0$, og stöðvast þar. Athugið að þessi vara verður ekki flutt áfram á borð $1$ með því að fara um færiband $1$.

Athugið að þetta sýnisinntak uppfyllir ekki takmarkanir neins undirverkefnis.

Meðal þeirra skráa sem hægt er að nálgast á vefsíðu keppninnar uppfyllir sample-02.txt takmarkanir undirverkefnis $1$, og sample-03.txt uppfyllir takmarkanir undirverkefnis $2$.