Zadanie https://pl.spoj.com/problems/KIP/13
Mój kod https://ideone.com/HqYmUM14 , jest za wolny. Czy można jakoś przyśpieszyć czy całkiem zmieniać pomysł ?
created
Jun '23last reply
Jun '23- 3
replies
- 279
views
- 3
users
- 2
links
W pierwszej kolejności proponowałbym wyłączyć synchronizację std z iostream (ios::sync_with_std(0)). Przy takim dużym wejść i wyjściu używanie cout << endl zabija performance.
Poza tym koncepcje wydaje się prawidłowa. Jeśli nie ma błędów w indeksach i zakresach, to powinno działać.
niestety nie pomaga, zamiana na scanf i printf również. Na temat indeksów i zakresów nie widzę błędów ale nie wiem…
W kwestii buforowanie wejścia i wyjścia, to sugerowałbym jeszcze wyłączyć powiązanie pomiędzy std::cin i std::cout przy pomocy std::cin.tie(nullptr) (bez tego operacje na cin powodują czyszczenie bufora cout).
W powyższym rozwiązaniu jest kilka zbędnych elementów które aż czterokrotnie zwiększają zużycie pamięci. Tylko jedna z zadeklarowanych tablic jest używana w rozwiązaniu. Dodatkowo tablica ta przechowuje strukturę w której używane jest tylko jedno z trzech pól.
Jeśli chodzi o same struktury danych, to drzewo Fenwicka byłoby tu nieco szybsze niż drzewo przedziałowe.
Suggested Topics
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 65 | Apr 2 |
| PP0504B - StringMerge - w języku C | Zbiór zadań | 5 | 164 | Jun '24 |
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 117 | Feb 1 |
| FR_08_11 - Gra w bańki | Zbiór zadań | 1 | 141 | Jun '24 |