Potwierdzam testy.

Mnie wczoraj system przyjął i ocenił zgłoszenie o 23:59:56 (edit: oczywiście chodzi o Rundę 4), więc zakładam że do 23:59:59 przyjmuje. Co się dzieje o 0:00:00 nie wiem.

potwierdzam

https://easyupload.io/yrs346

300 losowych testów z L <= 20.

Otóż nie, choć byłby to duży mózg czas. Napisałem generatorke testów (zapomniałem ustawić seeda więc tylko kilka testów było różnych spośród tych 101, na tym polegał fix), puściłem na niej rozwiązanie które nie weszło i naprawiałem rozwiązanie aż dało inne outy i wtedy weszło xd

Wow; napisałeś że testy pomogły ci znaleźć buga, mając na myśli buga którego dopiero znajdziesz, gdy się okaże że testy które wrzucasz są niepoprawne? :o

Dziękuję Juliusz za niepotwierdzenie xD podmieniłem link na sfixowane testy.

"Format *wejście* implikuje, że początkowe pozycje wszystkich samochodów"

Nie potwierdzam testow.

Paczka 101 semilosowych testów, które pomogły mi znaleźć buga:
https://drive.google.com/file/d/1jXKUqGonsveMXPK35mc4z9a70IuHjk9W/view?usp=sharing

Edit: fix testów xD

A żeby nie mieć O(mn*840), to dla każdej ulicy pionowej, to na początek dla każdego L liczę ora cykli świateł o długości L i dopiero jak już je mam, to wtedy wyliczam całościowy pattern w czasie O(840*8)

Ja tam mam złożoność O(8mn+840*8*(n+m)+q), a i tak 7.2s/9 mi zabrało. Aby mieć q, a nie jakie q log n, to ogólnie to jak sobie pomyślę o jednowymiarowym zadaniu, że idę w prawo i mam stan (i, t), tzn. jestem na polu i oraz reszta z dzielenia czasu przez 840 to t, to jak przejście do i+1 jest zablokowane, to idę do stanu (i, (t+1)%840), a jak nie to (i+1, t). Takie krawędzie tworzą las z 840 korzeniami postaci (m, t), ale zamiast po nim obskakiwać jumppointerami zgodnie z kierunkami krawędzi, to zapuszczam dfsa po grafie odwróconym i jak wchodzę do wierzchołka (i, t) to patrzę jakie są zapytania, które się zaczynają w takim stanie i po prostu odczytuję ile krawędzi typu (i,t)->(i, (t+1)%840) przeszedłem od czasu wyjścia z warstwy j, gdzie j to punkt docelowy danego zapytania.

@Marcin Mordecki Początkowo zrobiłem też vector<vector<vector<uint16_t>>>, ale najgłębszy wymiar był odpowiedzialny za skoki o 2^k, więc był krótki i do każdych 20-30 bajtów dokładało 24 bajty z samego konteenera:-) Zdązyłem walnąc prostą tablicę 3d, zapisująca w liniowej przestrzeni, nawet ustawilem wymairy tak, by praktycznie zawsze iterowało w najglebszej pętli po nahjglebszy wymiarze. Ale ~ polowa czasów zleciała.
Wszystko praktycznie identycznie jak opowiadający wyzej, cztery tablice n*840*liczba_poziomów. Pamieci starczało dla liczby poziomów >17.
Nie rozrózniałem przypadków testowych na kategorie (co też nie przeszkadza, bo jak zapytam tabelki o )ten drugi wymiar, ta od razu odpowie, że doszedłem w tej wspolrzednej.
Dla liczby poziomów = 11 dstało 6 punktów. Ale ostatecznie wysłałem z liczba poziomów 15, co na moim kompie i testach dawało lepsze wyniki, ale wtedy dostało 4. Będę musiał kiedyś popatrzeć, co tak niewydajnie robiłem. Trzeba było optymalizować, a nie "ponizej 8 sekund u mnie, to na sprawdzazrce się zmieści" :)

> Na początku trzeba policzyć dla każdej ulicy, czy da się przez nią przejść w danym czasie, co naiwnie jest N * M * NWW

Można osobno liczyć patterny mod 2, 3, ... 8 dla każdej ulicy, i dopiero na koniec zamienić na pattern modulo 840 dla całej ulicy.

Opcja pośrednia: liczyć patterny modulo 24 i modulo 35.

Potwierdzam