Problem F
Split Median
Languages
en
is
Það að finna miðjunginn í röðuðum lista er einfalt verk, og allt sem þarf að gera í þessu verkefni. Úr fyrirlestrunum veist þú auðvitað að það dugar að taka miðjustakið í listanum og það er einfaldlega svarið!
En því miður flækjast hlutir nú aðeins! Láki laumaðist inn í gögnin og skemmdi fyrir þér. Hann skipti listanum upp í tvo raðaða lista og faldi svo þá lista. Nú getur þú aðeins skoðað eitt stak í einu sem gerir það erfitt að skoða listana í heild sinni.
Skilafresturinn nálgast, svo þú þarft að finna miðjunginn fljótlega!
Gagnvirkni
Þetta er gagnvirkt verkefni. Lausnin þín verður keyrð á móti gagnvirkum dómara sem les úttakið frá lausninni þinni og skrifar í inntakið á lausninni þinni. Þessi gagnvirkni fylgir ákveðnum reglum:
Fyrst les forrit þitt línu með tveimur jákvæðum heiltölum $n$ og $m$, þar sem $2 \leq n+m \leq 100\, 000$. Dómaraforritið mun vera með tvær faldar runur $a_1, a_2, \dotsc , a_n$ og $b_1, b_2, \dotsc , b_m$. Svo er eftirfarandi endurtekið. Þú velur eina af þremur aðgerðum:
-
Prenta ? A i þar sem $i$ er vísir í fyrsta listann, þar sem fyrsta stak hefur vísi $1$. Svo les forrit þitt gildið $a_i$ sem dómaraforritið prentar.
-
Prenta ? B i þar sem $i$ er vísir í annan listann, þar sem fyrsta stak hefur vísi $1$. Svo les forrit þitt gildið $b_i$ sem dómaraforritið prentar.
-
Prenta ! x þar sem $x$ er gildið á miðjungnum. Eftir þessa aðgerð á forrit þitt að ljúka keyrslu.
Sérhver heiltala í listunum er á bilinu $-10^9$ til $10^9$, þar sem báðir endapunktar eru með. Ef $n + m$ er slétt eru tvö miðjungsstök og þau eru bæði tekin sem gilt svar.
Vertu viss um að gera flush eftir hvern leik, t.d., með
-
print(..., flush=True) í Python,
-
cout << ... << endl; í C++,
-
System.out.flush(); í Java.
Stigagjöf
Þú þarft að finna rétt miðgildi með því að nota minna en $2 \cdot (n+m)$ aðgerðir. Síðasta aðgerðin, þar sem þú tilkynnir svar þitt, er ekki talin með. Ef þú notar $n + m$ aðgerðir muntu fá $10$ stig af $100$ mögulegum. Að nota færri aðgerðir hækkar stig þín, en vöxturinn er ekki línulegur.
| Read | Sample Interaction 1 | Write |
|---|
3 4
? A 3
8
? B 1
2
? B 3
7
? A 1
1
? B 2
5
! 5
