Ja jeszcze inaczej to napisałem.

Sprawdzałem posortowane kolejno (od lewej strony) okręgi czy aby są styczne z którymś z poprzednich (który zaś styka się z lewą ścianą (bez)pośrednio). Dla każdego okręgu szukałem (dopóki nie znajdę, lub dopóki prawa ściana poprzedniego jest dalej lub na równi z lewą ścianą aktualnego) wszystkie okręgi. Jeśli było tak - sprawdzałem czy są styczne, jeśli były - sprawdzałem czy tamten był połączony z lewą ścianą. Oczywiście trochę optymalizacji coby nie szło jako k^2. Po zakończeniu spr. (jeśli udało się połączyć bądź z jakimś poprzednim (który łączy się z lewą ścianą) bądź z samą lewą ścianą) spr. czy łączy się aktualny z prawą - jeśli tak to nie można przejść i koniec pętli, jeśli nie to jedzie dalej lub - jeśli to koniec okręgów - można przejść.

Maxymalny czas: x (po 22)

@Paweł Michalak - Może i wygląda na k^2, ale praktycznie k^2 nigdy nie osiągnę w samym algorytmie, nawet blisko niego nie podejdę. Zapomniałem jedynie policzyć sortowania - k*log(k) (dla max testu to 3000 obrotów). Zakładając że każdy jest połączony z poprzednim mam 4k obrotów - czyli do 1mln trochę brakuje Do tego dochodzi jeszcze to, że w zależności od pozycji kolejnych okręgów badam tylko kilka okręgów ostatnich, więc szczerze wątpię aby dla maksymalnych danych zrobiło ten milion obrotów.

Przynajmniej tak mi się wydaje i rzucając kilka "najgorszych" testów dla algorytmu wykazuje, że łącznie z posortowaniem robi mniej obrotów niż k^2 A jak z czasem - zobaczymy, zawsze mogłem coś "zepsuć"

I to nie jest n^2?

I tak jak mówiłem - kolega ma k^2 z FIND i UNION (z tego co zrozumiałem) i ma ponad 2* wolniej

U mnie wszystko 0ms, a 3 ostatnie testy 3ms, 3ms i 9ms Pamięć stała 1052 dla każdego testu.

No ja miałem ostatni 59ms, ale coś musiałem tym przebałaganie pomylić i mam 9 WA

Jeśli już się chwalimy to ja mam na ostatnim 36ms z rozwiązaniem O(n^2log*n). To przecież tylko kosmetyczna różnica, limity były na tyle małe, że można było sobie pozwolić..

Źle to odebrałeś, po prostu stwierdziłem, że miałem rację mówiąc, iż nie jest to bliskie k^2. Za to z 2giej strony napisane od niechcenia trasy w miarę wolno czasem by przeszły, ale w 9 przypadkach dostałem WA (czekam na testy jak na razie, żeby zweryfikować błąd) .
Ale co racja to racja - limity były naprawdę duże w porównaniu do testów (lub testy małe ).

Wystarczyło stworzyć graf gdzie wierzchołkami są 2 boczne ściany "mapy" i koła, a krawędź łączy 2 koła lub koło i ścianę gdy mają punkty wspólne. Jeśli da się przejść z wierzchołka "ścianowego" lewego do prawego to odp jest nie, w przeciwnym wypadku tak.

Czyżby Ciebie też siódmy test honorowym punktem uraczył?

U mnie podobnie jak u Michała Z. Zrobiłem super wierzchołki lewą i prawą krawędź, graf gdzie ścieżka to stykające lub przecinające się okręgi. Potem dfs od lewego super wierzchołka.

Mam zero z powodu małego buga, ale teraz już działa 10/10.

@Up w 1szej rundzie też kilkanaście osób miało 3/10 tylko dlatego, że modulo mogło przyjmować wartość ujemną (a gdyby policzyć osoby, które nie wiedziały o tym, a po prostu się udało bo inaczej to napisali - ponad połowa pewnie miała by 3/10 ).