Czy ktoś opisałby jakieś zgrabne rozwiązanie tego zadania?

Wpadłem na coś takiego:
Z kolejki priorytetowej ściągam wszystkie odstępy między klientami w kolejności w jakiej będą znikać (po zniknięciu aktualizuję priorytet następnego odstępu). W ten sposób tworzę ciąg trójek (czas pieczenia zapiekanki, sumaryczny czas oczekiwania, przyrost czasu oczekiwania). Dla każdego piekarnika binsearchem szukam w tym ciągu najbliższego mniejszego czasu pieczenia i wyliczam wynik.
O((n+m)log n)
Niestety brakło czasu na zakodowanie :(

Podpinam się do pytania. Z racji tego, że już jest po rundzie chyba może już ktoś udostępnić.

Ja generalnie też "zabijałem" dziury - odstępy między klientami i łączyłem klientów we wspólne przedziały. Przejeżdżałem po rosnących d i dla każdego nowego d zabijałem dziury, które musiały być zabite. Po zabiciu dziury trzeba było sprawdzić prawą dziurę. Po zabiciu dziury, połączyłem przedziały więc nowy przedział będzie się rozrastał w prawo z nową prędkością - stąd sprawdzenie prawej dziury. Aktualizowałem jej nowy czas do zabicia, a jeśli trzeba ją było zabić teraz, to zabijałem i dalej na prawo. Wszystkie dziury przeznaczone do zabicia dla danego d załatwiałem od lewej do prawej. Przy okazji modyfikowałem odpowiednie wartości, tak że dało się wyliczyć czas oczekiwania wszystkich klientów - połączeni wcześniej klienci aktualizowali się z automatu, połączeni w danym momencie byli doliczani na bieżąco, a ci, co nie musieli być połączeni, rozrastali się spokojnie w lewo.

Kod wyszedł masakrycznie długi i w szczegóły nie będę się wdawał, ale słyszałem opinie, że zadanie było "proste w c**j", więc też jestem ciekaw prostego i eleganckiego rozwiązania.

Sam pomysł jest generalnie identyczny jak u pozostałych, jednak minimalnie zmieniłem interpretacje pewnych wartości - nie zmieniając wyniku.

W mojej interpretacji zapiekanke można zacząć piec dopiero po przybyciu klienta, a liczymy czasy czekania aż zapiekanka trafi do piekarnika zamiast aż go opuści.

Łatwo pokazać, że zawsze odpowiedzią jest identyczny harmonogram pieczeń jedynie przesunięty w prawo. Dzięki temu czasy rosną tylko w jednym kierunku.

https://hastebin.com/topudezuji.cpp

Kod dostał jedynie 7/10, ale prawdopodobnie przez overflow w 124 linijce (poprawiony w linku).

Grzegorz: kod z linku wszedłby na 10.

> W mojej interpretacji zapiekanke można zacząć piec dopiero po przybyciu klienta, a liczymy czasy czekania aż zapiekanka trafi do piekarnika zamiast aż go opuści.
>
> Łatwo pokazać, że zawsze odpowiedzią jest identyczny harmonogram pieczeń jedynie przesunięty w prawo. Dzięki temu czasy rosną tylko w jednym kierunku.

Pod warunkiem że przesuwasz moment włączenia piekarnika, bo nie dało się zacząć piec przed czasem 0, albo dodasz fejkowego klienta o czasie 0 (który sam nie będzie czekał, ale jego zapiekanka przepchnie pozostałe).

W moim podejściu w ogóle nie patrzyłem na same czasy tylko na różnice kolejnych 2, ale może tak jak wyżej byłoby prościej.

Odpowiednio przyżyłowane rozwiązanie działające w złożoności O(n*m) też wchodzi na 10 punktów ;)