1399. Sortowanie leksykograficzne [PLEXSORT]

Myślę, że to nie jest wina sorta, tylko samego algorytmu - pamiętaj, że słów jest ok. [tex]10^5[/tex] a liter w każdym do 1000, więc pesymistycznie sprawdzasz [tex]10^8[/tex] liter.

Edit: No dobra, sprawdzasz do [tex]4 \cdot 10^6[/tex] liter. Może to przez to (pamiętaj, że nie zrobiłem tego zadania).

Witam

Arcik:
Błędną odpowiedz otrzymujesz, bo we funkcji stringCompare masz niewłaściwy priorytet warunków (przy okazji: else nic nie wnosi przy returnach).
O dziwo na angielskim przechodzi, najwidoczniej zbyt mało dobrane testy się tam znajdują.
Po naprawieniu funkcji stringCompare otrzymasz przekroczony czas, a to z kolei przez powielanie pewnej niepotrzebnej operacji.

Po drobnych korektach Twoim kodem dostałem AC z czasem 6.16.

Pozdrawiam

Może nie powinienem zabierać głosu, bo nie mam ani pozytywnej ani negatywnej odpowiedzi na zadane pytanie. Nieużywałem do rozwiązania tego zadania drzewa trie, ani żadnego innego drzewa.
Użyłem qsort i szybki I/O a właściwie tylko szybki I/ i normalny /O

Hmm, rzeczywiście, nie zdążyłem zauważyć twoich editów - temat spadł zbyt nisko, a widząc datę ostatniego posta sprzed kilku dni, nie otwierałem go.

Nie mam zielonego pojęcia co z tamtym kodem było źle. Przepisałem go natomiast na czyste C oraz qsorta, po czym otrzymałem AC. Czy mógłbyś mi wysłać na PW (albo i na forum, jeśli to nie zespoiluje zadania) różnicę między kompilatorami, która zaważyła o wyniku? Ciekaw jestem, co też mogło mnie zatrzymać - tym bardziej że, o ile czegoś nie przeoczyłem, pisałem kod zgodny ze standardem, pozbawiony undefined behaviours itd.

Też nie wiem, ale to na pewno nie wielkość tablic. Ja mam/miałem, tak jak w specyfikacji zadania: char bufor [4000 000] i tab[100 000].
Jedynym podejrzanym miejscem wydaje mi się funkcja porównująca. Wg mnie jej szablon wygląda/wyglądał jakoś tak: cmp (const void *a, const void *b) i trochę trzeba się nagimnastykować, żeby wydobyć z tego, to co nam jest potrzebne - adresy porównywanych stringów. Dlaczego więc to się kompiluje i działa na ideone i lokalnie. Może to właśnie sprawa nowszych kompilatorów [i bibliotek] i w nowszych może to ukłon twórców kompilatorów w stronę programistów i ten szablon jest przeciążany na więcej sposobów i dostosowany do innego sposobu/sposobów pisania kodu? Może po skompilowaniu nowszym kompilatorem jest ok, a może tylko dla malutkich danych? Na SPOJ'u do tego zadania jest tylko stary c++ 4.00.8. Możnaby więc to jeszcze sprawdzić na najnowszym dostępnym na SPOJ'u kompilatorze. Jak to zrobić, bardzo prosto - zrobić sobie, jako problemsetter takie zadanie testowe i to przetestować. Jest to więc doskonała okazja, o wysłanie do adminów prośby o takie uprawnienia [problemsettera]. Czy mógłby to dla Ciebie ktoś zrobić? Możliwe, jednak nie ja, bo zostały mi odebrane, nawet nie wiem dokładnie dlaczego, takie uprawnienia - uprawnienia problemsettera ;-(

PS
Można też, poprosić autora zadania, o podłączenie nowszego kompilatora c++, a przy okazji także kompilatorów innych języków.

Być może jakże emocjonująca gra w węża wyczerpała mój dzisiejszy potencjał i jestem ślepy. Tak czy siak - błędu nie widzę. Według mnie wszystko śmiga a według SPOJa mam SIGSEGV.

Zastanawiam się, czy przyczyną nie są tablice stringów. Ale z drugiej strony - inni jakoś stringami to zadanie zaliczyli...

Stąd moja prośba o pomoc w lokalizacji wycieku pamięci.

Kod: https://ideone.com/YstVcX21
Zadanie: http://pl.spoj.com/problems/PLEXSORT/4

Jakoś - jest tu prawdopodobnie bardzo dobrym określeniem
Po pierwsze, skąd masz taką informację - przejrzałem ten wątek, a także jego pełniejszą wersję na starym forum i jakoś nie rzuciło mi się 100% potwierdzenie. Pamiętaj, że w C++ są dwa rodzaje stringów, C-string i klasa string. Ty użyłeś tych drugich, a pewnie nie wiesz do końca jak one działają?
Więc napisz i uruchom sobie taki programik:

   string a     
   while(1){
            cin >> a;
            cout << a.capacity() << ' '  << a.length() << endl;
        }

Wpisuj po kolei coraz dłuższe stringi, zaczynając od stringu o długości jeden, a na koniec znowu od 1.
DO tego programiku możesz dodać a.clear() i nic to nie zmieni. Możesz też dodać, przed pętlą, a.resize(wartość), czy a.reserve(wartość) [np wartość < 10] i sprawdzić co będzie wtedy, gdy dodamy dłuższy string. Zasada nie ulegnie zmianie.
Gdy to potestujesz, będziesz miał prawdopodobnie odpowiedź na swoje pytanie. Na takiej samej zasadzie działają też i inne kontenery z STL, a napewno vector.

PS
Twoje sortowanie dodatkowo pogłębia powyższy efekt - długie stringi mogą być wczytywane na początek tablicy, ale w trakcie sortowania mogą "powędrować" i zostać skopiowane nawet na koniec. Nawet, gdyby udało Ci się "opanować" sigsegv to i tak miałbyś takim sposobem zapewne tle.

PS 2
Zadanie można zrobić sortując same wskaźniki do stringów [możliwe, że nawet do tych klasowych z c++], a nie same stringi jako takie. Pisał wyraźnie o tym nawet autor zadania, właśnie w tym wątku na starym forum.

Hm... wiedziałem, że tak działają stringi, ale nie sądziłem, że to coś może popsuć. Ba - chciałem nawet użyć resize, ale powiększając już na początku każdy string do 1000 a idąc spać wymyśliłem, że może ewentualny problem z rozmiarami rozwiąże vector.

Cóż mogę rzec. Widocznie na tym polega różnica między średnimi a łatwymi, że w średnich zwykłe "a dam se stringa i byle jakiego sorta co by nie komplikować" (tak zinterpretowałem opisy ze starego forum) zwyczajnie nie działa. Wskazane jest też głębsze rozumienie konsekwencji zapisów zawartych w kodzie.

Znalazłem ciekawy kod rozwiązujący to zadanie w krótkim czasie. Są w nim stringi, ale użyte w sposób, którego nie rozumiem. Dodatkowo jest tam jakieś ext/rope, czego też nie znam. Wydaje mi się, że jego przestudiowanie jest w tej sytuacji wskazane.

Dziękuję za pomoc i oszczędzenie kilku dni myślenia (wczoraj w nocy przerobiłem już nawet string na char, ale i tak nie działało).