Fişierul intrare/ieşire:	interclasare.in, interclasare.out	Sursă	Lista lui Francu
Autor	Catalin Francu	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.075 sec	Limită de memorie	9216 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Interclasare

Se dau doi vectori de numere intregi: A cu N elemente si B cu M elemente. Sa se afle cel mai lung subsir crescator ce se poate obtine prin interclasarea acestor doi vectori. Reamintim ca o interclasare a doi vectori A=( a₁ , a₂, ..., a_m) si B=( b₁, b₂, ..., b_n ) este un vector C=( c₁ , c₂, ..., c_m+n ) care contine toate elementele lui A si B astfel incat a_i apare inaintea lui a_j si b_i apare inaintea lui b_j in C pentru orice i < j . Prin "subsir crescator" se intelege un subsir D=( c_i1, c_i2}, ..., c_i{~k) astfel incat i₁<$i₂<...<$i_k si c{_i1} < c{_i2} <...< c{_ik}.

Date de intrare

Pe prima linie a fisierului "interclasare.in" se va afla numarul N reprezentand numarul de elemente ale primului sir. Pe linia a doua se vor afla N numere reprezentand elementului primului sir. Pe linia a treia se va afla numarul M reprezentand numarul de elemente ale celui de-al doilea sir. Pe urmatoarea linie se vor afla cele M elemente ale celui de-al doilea sir.

Date de iesire

Pe prima linie a fisierului "interclasare.out" se va afla lungimea celui mai lung subsir crescator ce poate fi obtinut prin interclasarea celor doua siruri din fisierul de intrare. Pe linia a doua se vor afla N+$M$ elemente reprezentand sirul C, adica sirurile A si B interclasate in asa fel incat cel mai lung subsir comun din vectorul C sa aibe lungime maxima.

Restrictii

• $ 1 ≤ N , M ≤ 100 000$
• $ 1 ≤ a_i ≤ 100 000$ ptr orice 1 ≤ i ≤ N
• $ 1 ≤ b_i ≤ 100 000$ ptr orice 1 ≤ i ≤ M
• In caz ca exista mai multe solutii afisati oricare dintre ele
• Veti primi punctaje partiale pe fiecare test astfel:
  • 40% din punctaj daca prima linie este corecta.
  • 100% daca ambele linii sunt corecte

Exemplu

table(example). |_. interclasare.in |_. interclasare.out |
| 4
3 9 6 1
5
2 6 4 8 5
|
5
2 3 6 4 8 9 6 1 5
|

Explicatie

...

Cum se trimit solutii?