JOI Co., Ltd.:n tehtaassa on $N$ pöytää, jotka on numeroitu $0$:sta $N-1$:een. Tehtaassa on $N-1$ liukuhihnaa, jotka on numeroitu $0$:sta $N-2$:een. Liukuhihna $i$ ($0 \le i \le N-2$) yhdistää pöydän $A_i$ ja pöydän $B_i$. Se kuljettaa tuotteita yhdeltä pöydältä toiselle. Emme kuitenkaan näe kuljetussuuntaa. Jos jätämme liukuhihnojen suunnat huomiotta, jokainen pöytäpari on yhteydessä toisiinsa joidenkin liukuhihnojen kautta.

IOI-kun on tehtaan johtaja. Koska hän on unohtanut jokaisen liukuhihnan kuljetussuunnan, hän suorittaa seuraavan vaihesarjan useita kertoja.

1. Hän valitsee joukon liukuhihnoja ja kääntää valittujen liukuhihnojen kuljetussuunnat päinvastaisiksi.
2. Hän valitsee joukon pöytiä ja asettaa yhden tuotteen kullekin valitulle pöydälle.

3. Jokaiselle pöydälle, jolle on asetettu tuote, tapahtuu samanaikaisesti jompikumpi seuraavista.

   • Jos pöydältä ei lähde yhtään tuotteita kuljettavaa liukuhihnaa, mitään ei tapahdu.
   • Jos pöydältä lähtee tuotteita kuljettavia liukuhihnoja, jokin tällainen liukuhihna kuljettaa pöydällä olevan tuotteen. Tuote pysähtyy kyseisen liukuhihnan määränpäähän. Tuote ei liiku enää sen jälkeen.

4. IOI-kun tarkistaa jokaisen pöydän osalta, onko sillä yksi tai useampi tuote. Jos pöydällä on tuotteita, IOI-kun ottaa ne kaikki pois.

5. Jokaiselle liukuhihnalle, jonka suunta käännettiin vaiheessa 1., IOI-kun palauttaa sen suunnan. Sen suunnaksi tulee jälleen alkuperäinen suunta.

IOI-kun haluaa selvittää jokaisen liukuhihnan alkuperäisen suunnan suorittamalla yllä kuvatun vaihesarjan enintään $30$ kertaa.

Kirjoita ohjelma, joka saa tiedot liukuhihnojen yhdistämistä pöydistä ja toteuttaa IOI-kunin strategian jokaisen liukuhihnan alkuperäisen suunnan selvittämiseksi suorittamalla yllä kuvatun vaihesarjan enintään $30$ kertaa.

Toteutuksen yksityiskohdat

Sinun tulee palauttaa yksi tiedosto.

Tiedoston nimi on conveyor.cpp. Sen tulee toteuttaa seuraava funktio. Ohjelman tulee sisällyttää conveyor.h käyttämällä esikääntäjädirektiiviä #include.

Tiedostossa conveyor.cpp tulee toteuttaa seuraava funktio.

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

  Tätä funktiota kutsutaan vain kerran kutakin testitapausta kohden.

  • Parametri N on pöytien lukumäärä $N$.
  • Parametrit A, B ovat pituuden $N-1$ taulukoita, jotka kuvaavat liukuhihnojen yhdistämät pöydät.

  Ohjelmasi voi kutsua seuraavia funktioita.

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

    Tämän funktion avulla IOI-kun suorittaa toimenpiteet tehtaassa.

    • Parametri x on pituuden $N-1$ taulukko. Arvoilla $0 \le i \le N-2$ IOI-kun kääntää liukuhihnan $i$ suunnan, jos x[i] = 1, eikä käännä liukuhihnan $i$ suuntaa, jos x[i] = 0.
    • Parametri y on pituuden $N$ taulukko. Arvoilla $0 \le j \le N-1$ IOI-kun asettaa tuotteen pöydälle $j$, jos y[j] = 1, eikä aseta tuotetta pöydälle $j$, jos y[j] = 0.
    • Olkoon z tämän funktion paluuarvo. Se on pituuden $N$ taulukko. Arvoilla $0 \le j \le N-1$ pöydällä $j$ on yksi tai useampi tuote, jos z[j] = 1, ja pöydällä $j$ ei ole yhtään tuotetta, jos z[j] = 0.
    • Taulukon x pituuden tulee olla $N-1$. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [1].
    • Taulukon x jokaisen alkion tulee olla 0 tai 1. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [2].
    • Taulukon y pituuden tulee olla $N$. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [3].
    • Taulukon y jokaisen alkion tulee olla 0 tai 1. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [4].
    • Funktiota Query saa kutsua enintään $30$ kertaa. Jos sitä kutsutaan yli $30$ kertaa, ohjelmasi tulokseksi annetaan Wrong Answer [5].

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

    Tämän funktion avulla IOI-kun ilmoittaa kunkin liukuhihnan alkuperäisen suunnan.

    • Parametri a on pituuden $N-1$ taulukko. Arvoilla $0 \le i \le N-2$ liukuhihna $i$ kuljettaa tuotteita pöydältä $A_i$ pöydälle $B_i$, jos a[i] = 0, ja se kuljettaa tuotteita pöydältä $B_i$ pöydälle $A_i$, jos a[i] = 1.
    • Taulukon a pituuden tulee olla $N-1$. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [6].
    • Taulukon a jokaisen alkion tulee olla 0 tai 1. Jos tämä ehto ei täyty, ohjelmasi tulokseksi annetaan Wrong Answer [7].
    • Jos IOI-kun ilmoittaa jonkin liukuhihnan suunnan väärin, ohjelmasi tulokseksi annetaan Wrong Answer [8].
    • Funktiota Answer tulee kutsua täsmälleen kerran. Jos funktiota Answer kutsutaan useammin kuin kerran, ohjelmasi tulokseksi annetaan Wrong Answer [9]. Kun funktio Solve päättyy, jos funktiota Answer ei ole kutsuttu, ohjelmasi tulokseksi annetaan Wrong Answer [10].

Tärkeitä huomioita

• Ohjelmasi voi toteuttaa muita funktioita sisäiseen käyttöön tai käyttää globaaleja muuttujia.
• Ohjelmasi ei saa käyttää standardisyötettä eikä standarditulostetta. Ohjelmasi ei saa kommunikoida muiden tiedostojen kanssa millään menetelmällä. Ohjelmasi voi kuitenkin tulostaa virheenkorjaustietoja standardivirhetulosteeseen (standard error).

Kääntäminen ja testiajo

Voit ladata kilpailun verkkosivulta arkistotiedoston, joka sisältää esimerkkitsarkistimen (sample grader) ohjelmasi testaamista varten. Arkistotiedosto sisältää myös esimerkkilähdekooditiedoston ohjelmallesi.

Esimerkkitarkistin on tiedosto grader.cpp. Testataksesi ohjelmaasi aseta grader.cpp, conveyor.cpp ja conveyor.h samaan hakemistoon ja käännä ohjelmasi suorittamalla seuraava komento. Vaihtoehtoisesti voit suorittaa arkistotiedostossa olevan skriptin compile.sh.

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

Kun käännös onnistuu, syntyy suoritettava tiedosto grader.

Huomaa, että varsinainen tarkistin eroaa esimerkkitarkistimesta. Esimerkkitarkistin suoritetaan yhtenä prosessina, joka lukee syötetiedot standardisyötteestä ja kirjoittaa tulokset standarditulosteeseen.

Esimerkkitarkistimen syöte

Esimerkkitarkistin lukee seuraavat tiedot standardisyötteestä.

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

Arvoilla $0 \le i \le N-2$ pätee $C_i=0$, jos liukuhihna $i$ kuljettaa tuotteita pöydältä $A_i$ pöydälle $B_i$. Muussa tapauksessa pätee $C_i=1$.

Esimerkkitarkistimen tuloste

Esimerkkitarkistin tulostaa seuraavat tiedot standarditulosteeseen (lainausmerkit selkeyden vuoksi).

• Jos ohjelmasi todetaan oikeaksi, se ilmoittaa funktion Query kutsujen lukumäärän muodossa “Accepted: 22”.
• Jos ohjelmasi tulokseksi annetaan mikä tahansa Wrong Answer -tyyppi, esimerkkitarkistin tulostaa sen tyypin muodossa “Wrong Answer [4]”.

Jos ohjelmasi täyttää usean eri Wrong Answer -tyypin ehdot, esimerkkitarkistin ilmoittaa niistä vain yhden.

Esimerkkitarkistimessa niistä liukuhihnoista, jotka kuljettavat tuotteita pöydältä, jolle tuote on asetettu, tuotteen kuljettava liukuhihna valitaan tasaisesti ja satunnaisesti näennäissatunnaisluvuilla, joiden tulokset eivät muutu eri suorituskeroilla. Voit vaihtaa näennäissatunnaislukujen siemenluvun (seed) suorittamalla esimerkkitarkistimen antamalla sille ensimmäiseksi kokonaislukuargumentiksi luvun seuraavasti.

./grader 2023

Arviointia koskevia huomioita

Joissakin testitapauksissa varsinainen tarkistin on mukautuva (adaptive). Tämä tarkoittaa, että tarkistimella ei ole alussa kiinteää vastausta, vaan se vastaa aiempien Query-funktiokutsujen perusteella. On taattua, että on olemassa ainakin yksi vastaus, joka ei ole ristiriidassa minkään tarkistimen antaman vastauksen kanssa.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

• $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$).
• Jos jätämme liukuhihnojen suunnat huomiotta, jokainen pöytäpari on yhteydessä toisiinsa joidenkin liukuhihnojen kautta.

Osatehtävät

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

Esimerkkiviestintä

Tässä on esimerkkisyöte esimerkkitarkistimelle sekä sitä vastaavat funktiokutsut.

Syöte 1

3
0 2
2 1
1 0

Esimerkkifunktiokutsut

Ensimmäiselle funktion Query kutsulle toinen mahdollinen paluuarvo arvon [1, 0, 0] lisäksi on [0, 1, 0].

Toiselle funktion Query kutsulle pöydällä $0$ oleva tuote kuljetetaan pöydälle $2$ liukuhihnaa $0$ pitkin, ja se pysähtyy sinne. Huomaa, että tätä tuotetta ei kuljeteta edelleen pöydälle $1$ liukuhihnaa $1$ pitkin.

Huomaa, että tämä esimerkkisyöte ei täytä minkään osatehtävän rajoituksia.

Kilpailun verkkosivulta saatavista tiedostoista sample-02.txt täyttää osatehtävän $1$ rajoitukset ja sample-03.txt täyttää osatehtävän $2$ rajoitukset.