Czy ktoś mógłby napisać jaka jest poprawna odpowiedź do ostatniego testu przykładowego w zadaniu działka?

For english speakers: Could somebody please provide the correct answer for the last example test in task dzialka: dzi0c?

I have the very same problem and I've already wasted a few testruns trying to figure the reason out. I still don't understand it at all.

Polish version: Mam ten sam problem i zmarnowałem już kilka testrunów, by dowiedzieć się o co chodzi. Wciąż nie rozumiem.

Polish translation of the post above: Sprawdzaczki są dziwnie wolne. Lokalnie mam 2s na 20 instancjach dla planszy 40k x 40k, a submitnięte jako test programu działa 12 sekund. Ktoś ma ten sam problem?

I find the judge machine is strangely slow..
On my computer, my program can get the answer of a 40000*40000 size input within 2s using 20 nodes. But it ran 12 seconds when I submitted it to problem test.
Is there anyone have this strange problem too?

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

Potwierdzam testy. Na losowym maxteście mam 0.71s.

Potwierdzam wszystkie trzy paczki.

potwierdzam wszystkie 3 paczki

Też potwierdzam obie paczki.

> 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.

Grzegorz: kod z linku wszedłby na 10.

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).

Te też potwierdzam.

Bug ma co najmniej 2 lata :P
https://sio2.mimuw.edu.pl/c/pa-2015-1/forum/27/411/

Jeszcze 10 testów, t=1 i n=1800-2000: https://www.dropbox.com/s/tdyr02rw41xgdgg/tests_tak.zip?dl=0
Tamten 1.out za sekundę dodam.

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.