Link do zadania5

Mój pomysł na zadanie jest taki aby na początku zmapować sobie wszystkie wczytane litery z podanego stringa.
Kluczem w mapie jest litera, a wartością lista pozycji na jakich ta litera występuje.
Przy zamianie liter pobieram sobie indeksy zamienianych liter z mapy, podmieniam odpowiednie litery i aktualizuję mapę.
Czyli złożoność czasowa zamiany liter wynosi O(1) Jakim więc cudem algorytm nie przechodzi próby czasu.i wykłada się na 7 teście? Wygląda na to że samo mapowanie liter jest zbyt wolne…
Odniesie się ktoś do tego?
Konstruktywna krytyka również mile widziana.

Robię to poprzez wbudowaną metodę:

    list1.remove(wartosc1)
    list1.append(wartosc2)
    list2.remove(wartosc2)
    list2.append(wartosc1)

Wiem że set() byłby szybszy, ale z setu nie można pobrać indeksu na którym występuje szukany element.

Nie zastanawiałem się nad tym, nie wiem jak działa wbudowana metoda usuwania, ale masz rację z pewnością to trochę trwa. Zastąpiłem więc remove() poprzez del, które usuwa po indeksię więc dużo szybciej.
Niestety wstawienie i sortowanie później już jest nie do przejścia…

Czyli cały algorytm jest do niczego? Nieprawdopodobne żę da się coś szybszego wymyślić

Wydaje mi się jednak że cały algorytm jest zbyt wolny, bo najlepszy wyniki wynosi 0.23s, a jak przepisałem do C++ mój algorytm to też nie wyrabia się w czasie. Użyłem mapy<char, set>.