7252번 - Rikiavimas 서브태스크다국어인터랙티브

Jonas su Artūru žaidžia žaidimą. Jonas išdėlioja dvi kortelių sekas, kiekvienoje po N kortelių. Ant kiekvienos kortelės užrašytas sveikasis skaičius kuris gali būti nuo 1 iki N. Kiekvienoje sekoje visi skaičiai sutinkami lygiai vieną kartą.

Artūras kortelių nemato ir jo tikslas yra sužinoti kokie skaičiai užrašyti ant kiekvienos kortelės.

Jis gali daug kartų atlikti tokią užklausą: pasirinkti kortelę A iš pirmosios sekos, kortelę B iš antrosios ir paklausti Jono, kuri iš jų yra didesnė. Jonas į tokį klausimą jam atsako „A didesnė už B“, „B didesnė už A“, arba „kortelės vienodos“.

Artūrui šis žaidimas pasirodė labai sudėtingas, tad su Jono sutikimu jis paprašė tavo pagalbos. Padėk Artūrui sugalvoti strategiją, kaip sužinoti koks skaičius užrašytas ant kiekvienos kortelės atliekant kuo mažiau užklausų.

Ši užduotis yra interaktyvi! Jums reikės rašyti užklausas, o sistema į jas atsakinės.

Pirmoje įvesties eilutėje pateiktas skaičius N – kiekvienos kortelių sekos ilgis.

Toliau galite pateikti užklausas. Užklausa pateikiama išvedant (cout/printf) eilutę

? a b

Eilutė pradedama klaustuku ir nurodomi du tarpais atskirti sveikieji skaičiai 1 ≤ a, b ≤ N, kur a yra kortelės iš pirmosios sekos numeris, o b – kortelės iš antros sekos numeris.

Po užklausos pateikimo, sistema atspausdins skaičių ats:

• ats = -1 reiškia, kad a-oji pirmosios sekos kortelė mažesnė už b-ąją antrosios sekos kortelę.
• ats = 0 reiškia, kad ant abiejų kortelių užrašyti vienodi skaičiai.
• ats = 1 reiškia, kad a-oji pirmosios sekos kortelė didesnė už b-ąją antrosios sekos kortelę.

Atlikę visas užklausas išveskite Jono išdėliotas kortelių sekas:

• Pirmoje eilutėje išveskite vienintelį simbolį ! (šauktukas).
• Antroje eilutėje išveskite tarpais atskirtus skaičius x₁, ..., x_n, kur x_i yra skaičius, užrašytas ant i-osios pirmosios sekos kortelės.
• Trečioje eilutėje išveskite tarpais atskirtus skaičius y₁, ..., y_n, kur y_i yra skaičius, užrašytas ant i-osios antrosios sekos kortelės.

Jei užklausą pateiksite neteisingu formatu (pvz. po klaustuko išvesite tris skaičius vietoje dviejų) arba atliksite per daug užklausų, įvestyje bus pateiktas skaičius -2 ir Jūsų programa turi baigti darbą.

Kitu atveju (tęsiant išvedimą/įvedimą po -2 nuskaitymo) programos vykdymas sistemoje bus nutrauktas ir pateiktas pranešimas:

Vykdymas nutrauktas (tai galėjo įvykti viršijus atminties ribojimus).

Užtikrinkite, kad po kiekvienos užklausos jūsų išvestis iš karto pasiektų sistemą: atlikę užklausą, C++ kalboje naudokite cout << endl; arba cout.flush();, o C kalboje – fflush(stdout);.

Tarkime pirmosios sekos kortelės yra 1 3 2, o antrosios – 2 1 3. Tokiu atveju galimas toks sprendimas:

Visiems testams galioja ribojimai 1 ≤ N ≤ 200.

Visoms užklausoms galioja −1 ≤ ats ≤ 1 (jei jūsų programa pateikė per daug užklausų ats bus -2, nuskaičius šį skaičių programa turi sustoti daryti užklausas). 1 ≤ a, b ≤ N