Rezolvare PBinfo #2892

Cătălin lucrează la o firmă de transport de marfă. El se ocupă de planificarea traseelor pe care circulă camioanele. Există N trasee pe care pot merge camioanele, pe fiecare traseu poate circula cel mult un camion, iar acest camion nu poate depăși o limită de greutate ai. Firma deţine M camioane, fiecare camion poate circula pe maxim un traseu şi are o greutate bi. Ajutați-l pe Cătălin să planifice camioanele pe trasee în așa fel încât să poată circula cât mai multe camioane.

Cerința

Determinați numărul maxim de camioane care pot circula în același timp pe trasee și afișați o modalitate de a distribui camioanele pe trasee pentru a obține acest maxim.

Date de intrare

Fișierul de intrare camioane.in conţine pe prima linie două numere naturale N și M, reprezentând numărul de trasee, respectiv numărul de camioane. Pe următoarea linie se află N numere, a i-a valoare reprezentând limita de greutate a traseului cu indicele i. Pe următoarea linie se află M numere, a i-a valoare reprezentând greutatea camionului i.

Date de ieșire

Fișierul de ieșire camioane.out va conţine pe prima linie numărul maxim de camioane ce pot circula în același timp pe trasee. Pe a doua linie vor fi scrise N numere: al i-lea număr este 0 dacă pe traseul cu indicele i nu circulă nici un camion, sau un număr j (1 ≤ j ≤ M) dacă pe traseul i circulă camionul cu indicele j. Dacă există mai multe soluții, afișați oricare dintre ele.

Restricții și precizări

• 1 ≤ N, M ≤ 100.000
• 1 ≤ ai ≤ 1030 pentru 1 ≤ i ≤ N
• 1 ≤ bi ≤ 1030 pentru 1 ≤ i ≤ M
• Pentru teste în valoare de 70 de puncte 1 ≤ ai, bi ≤ 1018 dintre care: pentru 10 puncte N = M = 2 și pentru alte 20 puncte N = M și N, M ≤ 10.

Exemplu:

camioane.in

6 9
105 15 6 8 24 77
79 5 200 66 180 7 101 108 85

camioane.out

4
7 6 0 2 0 4

Explicație

Pot circula maxim 4 camioane în același timp. Pe traseul cu numărul 1 poate circula camionul cu indicele 7, pe traseul cu numărul 2 poate circula camionul cu indicele 6, etc. Mai există și alte soluții.