Tämä tehtävä on vuorovaikutteinen. Jokaisen rivin tulostamisen jälkeen sinun tulee tyhjentää tulostuspuskuri (flush). Voit käyttää cout << flush C++:ssa, System.out.flush() Javassa ja sys.stdout.flush() Pythonissa. Sinun on noudatettava tarkasti Vuorovaikutus-osion ohjeita; muuten voit saada tuomioksi väärän vastauksen (wrong answer), aikarajan ylityksen (time limit exceeded) tai muun virheen.
Koska työ kaivoksessa on raskasta ja aikaa vievää, kääpiöt päättivät hakea apua joidenkin tehtäviensä automatisointiin. Heidän nykyisenä tehtävänään on luokitella $N$ mineraalia (jotka on numeroitu luvuilla $1$:stä $N$:ään) eri luokkiin. Auttaakseen tässä Työläiskääpiö on asentanut uuden liukuhihnan. Kääpiöt voivat lisätä mineraalinäytteitä hihnan alkuun ja poistaa niitä sen lopusta (eli poistaa ne mineraalit, jotka on lisätty aikaisimmin).
Valitettavasti tällä liukuhihnalla ei ole tietokantaa, joten se ei pysty tunnistamaan minkään sillä olevan mineraalin luokkaa. Sillä on kuitenkin toinen hyödyllinen ominaisuus: se näyttää, kuinka monta eri mineraaliluokkaa hihnalla on kulloinkin. Osoittautuu, että tämä riittää kaivokselle, sillä kääpiöiden ei tarvitse tietää kunkin mineraalin luokkaa: heidän tarvitsee vain erotella mineraalit saman luokan kasoihin.
Voitko auttaa kääpiöitä ratkaisemaan tämän tehtävän liukuhihnan avulla?
Vuorovaikutus
Mineraalien luokat on kiinnitetty alussa eivätkä ne riipu tehdyistä kyselyistä.
Lue ensin rivi, joka sisältää yhden kokonaisluvun $N$, luokiteltavien mineraalien lukumäärän. Sen jälkeen voit suorittaa seuraavan kahden tyyppisiä operaatioita:
+ id— mineraali, jonka tunniste onid, lisätään liukuhihnan alkuun.-— liukuhihnan lopussa oleva mineraali poistetaan. Jos hihna on tyhjä, mitään ei tapahdu.
Jokaisen operaation jälkeen liukuhihna tulostaa yhden rivin, joka sisältää sillä hetkellä hihnalla olevien eri luokkien lukumäärän.
Tulostaaksesi vastauksen tulosta ensin rivi, joka sisältää merkin ! ja sen perässä luvun $k$, joka on kaivoksessa olevien eri luokkien lukumäärä. Tulosta sitten $k$ riviä, joista jokainen kuvaa yhden luokan. Jokaisen rivin tulee sisältää luku $c_i$ ja sen perässä $c_i$ kyseiseen luokkaan kuuluvan mineraalin tunnistetta. Jokaisen $N$ mineraalista on esiinnyttävä täsmälleen yhdessä luokassa. Voit tulostaa luokat ja kunkin luokan sisällä olevat mineraalit missä tahansa järjestyksessä.
Muista tyhjentää tulostuspuskuri (flush) jokaisen operaation ja vastauksen kirjoittamisen jälkeen. Muista laittaa välilyönnit lukujen ja symbolien +, -, ! väliin. Sinun on luettava kaikki syöte interaktorilta.
Rajoitukset
$1 \le N \le 500$, voit suorittaa enintään $35\,000$ operaatiota.
Esimerkit
Syöte 1
3 1 2 2 2
Tuloste 1
+ 1 + 2 + 3 - ! 2 2 1 3 1 2
Huomautus
Ensimmäisessä esimerkkitestissä $N = 3$ ja mineraalien $1, 2, 3$ luokat ovat vastaavasti $1, 2, 1$.
Paikallinen testaus
Files-osiosta löydät tiedoston A.zip, joka sisältää esimerkkitestit ja tarkistimen grader.cpp. Testataksesi ratkaisuasi käännä se ja anna sitten testin nimi ja suoritettava tiedostosi käännetylle ./grader-ohjelmalle:
./grader [test] [executable]
Esimerkiksi: ./grader 0b.in ./abc
Esimerkkitarkistimen ei taata käyttäytyvän täysin samalla tavalla kuin virallisen tarkistimen. Kumpikaan niistä ei kuitenkaan ole mukautuva (adaptive).