jaka była wzorcówka?
Ja zrobiłem zmodyfikowanego bubble sorta, więc tylko 5 pkt, chociaz mało brakowało do kilku więcej, bo limity były duże.
A bubble sorta względem docelowej pozycji, bo właściwie to tylko kolejność się liczyła. No i takie robie swapów dwóch kolejnych, dopóki się da + online sprawdzenia czy na obecnym etapie już wiadomo że się nie da. Z optymalizacji to coctailSort i spamiętywanie że krańce tablicy są posortowane (źródło wiki:d)

Oczywiste jest, że samochody mogą zamienić swoją kolejność tylko wtedy, gdy ich łączna długość jest mniejsza lub równa szerokości parkingu. Zatem należy sprawdzić czy istnieje taka inwersja samochodów, że początkowo samochód A jest przed B, a potem odwrotnie, a oba te samochody są zbyt długie, by się wyminęły.

Ja to zrobiłem MergeSortem. W każdym kroku mając dwie podtablice posortowane (i sprawdzone, czy każdą z nich dało się poprawnie posortować), wystarczyło je połączyć w jedną, posortowaną. Nazwijmy lewą tablicę left[], a prawą right[], wreszcie tymczasową, dużą tablicę arr[].
Zgodnie z MergeSortem, wrzucamy do arr[] mniejszą z wartości left[i], right[j], gdzie i oraz j są ilościami już wrzuconych elementów z poszczególnych podtablic. W każdym momencie musimy jednak pamiętać maksymalny wrzucony element z tablicy right[], a w momencie wrzucania elementu z left[] porównujemy, czy długość wrzucanego samochodu jest poprawna, tj. czy max_right+długość_aktualnego_samochodu<=szerokość parkingu. Jeśli chociaż raz ten warunek jest fałszywy, zwracamy fałsz, w przeciwnym wypadku prawdę.
Złożoność jest taka, jak sortowania MergeSortem, czyli O(nlogn).
Nie wspomniałem o tym co prawda, ale oczywiście kryterium porównującym samochody jest ich końcowa pozycja: samochód A<samochód B wtedy i tylko wtedy, gdy samochód A ma być ustawiony na miejscu<od żądanego miejsca B.

Można też dla każdego samochodu policzyć najbliższego sąsiada w lewo i w prawo, z którym się nie może wyminąć i prawdą jest, że jeśli nowy porządek zachowuje takie trójki to da się go osiągnąć.
Konieczne jest tu drzewo przedziałowe albo set, więc złożoność nlogn.

Ja utrzymuję w drzewie (mapie) pary (x,w) w taki sposób by dla rosnących x-ów, w były malejące.

By uniknąć ifów mapa na początku zawiera: (-oo,oo), (oo,0). Wówczas opisane pary (x_j,w_j) oraz (x_k,w_k) zawsze istnieją.

Wstawienie nowej pary (x_i,w_i) wygląda następująco:
(1) znajdujemy (x_j,w_j) o najmniejszym x_j, x_j >= x_i. Jest to najszerszy samochód, który musimy ominąć. Jeśli się nie da to NIE.

(2) jeśli w_i > w_j dodajemy do drzewa parę (x_i,w_i). Jeśli x_i == x_j kasujemy parę (x_j,w_j) (lub po prostu zastępujemy jeśli użyliśmy mapy).

Jeśli dodaliśmy/zastąpiliśmy parę w kroku (2) wtedy:
(3) bierzemy parę (x_k,w_k) o największym x_k, x_k < x_i. Jeśli w_k <= w_i kasujemy parę (x_k, w_k). Jeśli usnęliśmy parę powtarzamy krok (3).

Oczywiście x-y, które wstawiamy to minimalny x samochodu w jednej z pozycji, a wstawiamy w kolejności niemalejących minimalnych x-ów w drugiej.

Sortowałem po min(x1,x2) zarówno ciąg początkowy, jak i końcowy. Aby sprawdzić czy kolejność początkową można zamienić na końcową, przesuwałem początkowy ciąg "w nieskończoność" a następnie w kolejności, w jakiej mają stać wysyłałem samochody znów na początek parkingu.
Na drzewie przedziałowym (typu max), zawierającym wysokości samochodów sprawdzałem czy wśród samochodów na pozycjach (w tej nieskończoności) od 0 do i-1 jest taki, że uniemożliwi przejazd na początek parkingu. Oczywistym jest, że wystarczy sprawdzić największy, więc zapytanie to miało złożoność O(lg n). Następnie aktualizowałem drzewo, zamieniając wysokość i-tego samochodu na zero, też w czasie O(lg n). Wykonywałem to dla wszystkich samochodów, zatem złożoność taka, jak sortowania. O(n lg n).
Rozwiązanie całkiem przyjemne i krótkie, ponad połowę kodu zabrała mi implementacja drzewa przedziałowego.

@Michał Włodarczyk "Można też dla każdego samochodu policzyć najbliższego sąsiada w lewo i w prawo, z którym się nie może wyminąć i prawdą jest, że jeśli nowy porządek zachowuje takie trójki to da się go osiągnąć.
Konieczne jest tu drzewo przedziałowe albo set, więc złożoność nlogn."
Ale nie jest prawdą, że jeśli da się go osiągnąć, to zachowuje takie trójki. Przykład - samochody szerokości 2,3,4 dla parkingu o szerokości 5. Można osiągnąć układ 3,2,4, ale wcześniej najbliższy po lewej dla tego szerokości 4 był szerokości 3, a teraz jest 2 (i oba z nim kolidowały).

Można to jednak poprawić. Moje rozwiązanie jest następujące:
Sortuję oba ciągi samochodów po pozycji na parkingu, następnie dla każdego z przejść początkowego i końcowego ciągu do przodu i do tyłu (razem cztery przejścia) buduję sobie malejący stos (np. na tablicy, by dało się szybko wyszukiwać) tych samochodów, które przekraczają połowę szerokości parkingu. Dodając nowy samochód:
- szukam najmniejszego z samochodów na kolejce, który "koliduje" z obecnym i wpisuję go jako "sąsiada" dla tego przejścia (jeśli nie było dotychczas żadnego, który by kolidował, samochód zostaje bez "sąsiada")
- jeśli dany samochód przekracza połowę szerokości parkingu, dodaję go do kolejki, kasując wszystkie nie szersze od niego po drodze
Można przestawić samochody wtedy i tylko wtedy, gdy są identyczne zarówno oba ciągi skonstruowane przy przechodzeniu do przodu, jak i przy przechodzeniu do tyłu.

Pseudo-dowód: Załóżmy, że można przestawić samochody, a my powiedzieliśmy, że nie można, tzn. nasze ciągi sąsiadów się gdzieś różniły, tzn. sąsiad dla pewnego samochodu X wcześniej był A, a potem B. Jednak taka sytuacja jest niemożliwa, bo albo A musiałby się zamienić z X miejscami, co jest niemożliwe, bo ze sobą kolidują, albo A musiałby się zamienić miejscami z B, co jest również niemożliwe, bo oba są szersze od połowy parkingu.
Załóżmy teraz odwrotnie, że przestawiliśmy samochody A i B, które ze sobą kolidowały, a skonstruowane ciągi są identyczne. Możemy przyjąć bez straty ogólności, że A ma szerokość przekraczającą połowę szerokości parkingu. Rozważmy "sąsiada" B od strony A (tzn. przy przejściu do przodu, jeśli A jest po lewej stronie B i przy przejściu do tyłu w przeciwnym przypadku). Tym sąsiadem nie może być A, bo oznaczałoby to, że wcale nie zamieniliśmy miejscami A i B (pamiętajmy, że ciągi sąsiadów były identyczne). Jest to więc inny samochód C o szerokości przekraczającej połowę szerokości parkingu i takiej, że C i B ze sobą kolidują. To jest jednak również niemożliwe - teraz A jest z drugiej strony B, a C było najbliższym przekraczającym połowę szerokości parkingu z tej pierwszej strony, a więc A i C też musiały się minąć, co jest niemożliwe.

To rozwiązanie ma zaletę, że jest proste - wykorzystujemy tylko sortowanie i wyszukiwanie binarne.

@Michał Szostek

Pisząc 'zachowuje takie trójki' miałem na myśli, że nie zmienia w nich kolejności. W Twoim przykładzie wystarczy zachować porządek pomiędzy 4 a jego lewą blokadą(3) oraz pomiędzy 2 a jego prawą blokadą(4)