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.

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

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 :(

W paczce Krzyśka brakuje pliku 1.out, ale poza tym to potwierdzam obie paczki.

Potwierdzam, dzięki za testy. Poniżej przerobione testy Mateusza tak, żeby zwykle dawały "NIE". Uwaga: występuje t > 100, ale nie przekracza 1000.
https://www.dropbox.com/s/i1cj6i1x81yo2mk/tests_nie.zip?dl=0

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

Potwierdzam testy.

Daję 300 średnich testów od siebie, ale było by miło, gdyby ktoś jeszcze jakieś zrobił, mimo, że te ode mnie są w miarę sensowne, nawet te, gdzie odpowiedź to NIE. https://www.dropbox.com/s/f8wwbydqlaiiomz/3Btesty.zip?dl=0

Drudzy będą przedostatnimi i przedostatni drugimi

Ostatni będą pierwszymi i pierwsi ostatnimi...

What the f&*(, co się dzieje z tymi postami? Widziałem tego i był legitny, a mi wcześniej został bezsensownie ukryty post w innym temacie.

Testrun, w którym można sobie własnoręcznie ustawić zużycie pamięci.

Aktualnie mogę tylko strzelać jak blisko limitu jest mój iloczyn na testrunie, a lokalnie to 8MB mi nie pozwala nawet na uruchomienie programu (bo jakieś pierdoły, error while loading shared libraries). A dopóki człowiek nie wepcha w ten limit na testrunie, to też nie wie jak blisko jest i czy brakuje eps czy trzeba kilkukrotnie zbić.

Potwierdzam testy.

Potwierdzam, 1.44s na losowym maxteście na sio

Potwierdzam.