Robiłem zadanie, które z początku wydawało mi się banalne, zabrało mi wiele dni na rozmyślanie jak je wykonać i po zrobieniu go na tak zwaną "piechotę" czyli linowym przeszukiwaniu tablicy właśnie te kilka dni rozmyślam jak wykonać szukanie binarne w tym przypadku, gdyż nie wiem co zrobić gdy element nie znajduje się w tablicy a muszę podać jakąś wartość i pomimo kombinowania z wieloma ifami do niczego nie doszedłem. Z wyszukiwaniem binarnym nigdy nie miałem do czynienia więc znam tylko samą zasadę działania ale właśnie problem tkwi w tym, że nie wiem do zrobic z elementami które w tablicy się nie pojawiają.
Oto zadanie:
W Bajtocji wybudowano wysoką wieżę. Wejście na wieżę składa się z schodków, a każdy schodek ma pewną wysokość.
Bajtocką wieżę chce odwiedzić mieszkańców. Każda z osób posiada pewien wzrost, który pomaga w pokonywaniu kolejnych schodków. Aby mieszkaniec Bajtocji mógł wejść na pewien schodek, to musi być wyższy od wysokości schodka. Jeśli pewien schodek jest nie do przejścia przez mieszkańca, to zatrzymuje się on w danym miejscu na wieży - wyżej nie będzie mógł wejść.
Znając wysokości kolejnych schodków i osób zwiedzających wieżę chcielibyśmy wiedzieć, w którym miejscu zatrzyma się każdy mieszkaniec Bajtocji.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite (), oznaczające odpowiednio liczbę schodków prowadzących na wieżę oraz liczbę mieszkańców chcących odwiedzić wieżę. Kolejny wiersz zawiera liczb całkowitych () , gdzie oznacza wysokość -tego schodka. Pierwszy schodek znajduje się na samym dole wieży, a każdy kolejny wyżej od poprzednich. Następny wiersz wejścia zawiera liczb całkowitych ( ), gdzie oznacza wzrost -tego mieszkańca.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać liczb całkowitych , gdzie oznacza maksymalny numer schodka, na który może wejść -ty mieszkaniec Bajocji.
Przykład
Dla danych wejściowych:
3 6
2 5 1
1 2 3 4 5 6
poprawną odpowiedzią jest:
0 0 1 1 1 3