KC022 - Statystyka pozycyjna - Czas 0.00

[kamfeth]

Witam! Próbuje uzyskać czas 0.00 dla zadania “Statystyka pozycyjna”

SPOJ.com - Problem KC022

Szukam pomocy, a mianowicie mój kod jest w stanie wygenerować odpowiedzi w czasie 0.02, jednak gdyby był w stanie robić to o dwie setne szybciej to byłbym bardziej zadowolony Poszukuje podpowiedzi, wskazówek, które pomogłyby mi zoptymalizować mój kod do czasu 0.00.

KOD USUNIETY
`
Czy znalazłaby się jakaś osoba, która mogłaby mi doradzić w kwestii tego jak jeszcze mógłbym przyśpieszyć działanie tego kodu? Jestem też świadomy, że używanie funkcji printf() nie ma większego sensu, jeżeli wyłączyłem już synchronizacje, ale przy obiekcie cout czas pozostaje praktycznie bez zmian i tak.

Pozdrawiam!

[tarpauwatratar]

1. fastIO
2. nie jestem przekonany czy string to najlepszy pomysł - na ogół pozbycie się stringa daje realne przyspieszenie
3. tak teoretycznie sortować można w O(n), czego std::sort nie potrafi
4. wyboru k-tej liczby w zbiorze też można dokonać w O(n)

Nie wnikam w to co robisz w tym kodzie, ale myślę, że te punkty są dość uniwersalne i znajdziesz w nich coś dla siebie

[kamfeth]

Dzięki! Usuwam na razie mój kod i później jeszcze raz siądę do tego problemu myśląc o Twoich wskazówkach.

[tarpauwatratar]

Na pewno opłaci Ci się i może nawet wystarczy pierwszy punkt. Drugi może wymagać trochę roboty, a trzy i cztery niekoniecznie są możliwe do zastosowania (zależy od zakresów danych itp).

[kamfeth]

Nie wiem do końca jakie metody fast I/O mogę jeszcze zastosować będąc szczerym. Pomyślałem natomiast o tym, żeby stringa zastąpić tablicą vector o typie int lub char, wtedy pewnie kod byłby krótszy i nie używałbym tylu pętli co też pewnie pomogło by, ale kiedyś czytałem, że vectory są ogólnie wolne, więc nie wiem czy to dobry pomysł. Na razie tylko myślę, bo nie mam dostępu do komputera

[mariusz193]

Na razie tylko myślę, bo nie mam dostępu do komputera

tak właśnie powstają najlepsze programy

[tarpauwatratar]

Nie wiem do końca jakie metody fast I/O mogę jeszcze zastosować będąc szczerym

Jakiekolwiek http://www.algorytm.edu.pl/fast-i-o.html

Pomyślałem natomiast o tym, żeby stringa zastąpić tablicą vector o typie int lub char, wtedy pewnie kod byłby krótszy i nie używałbym tylu pętli co też pewnie pomogło by, ale kiedyś czytałem, że vectory są ogólnie wolne, więc nie wiem czy to dobry pomysł.

vector to praktycznie rzecz ujmując dynamiczna tablica. Dynamiczność daje dużą wygodę, ale kosztuje czas na sprawdzaniu czy nie jesteś poza zakresem i ewentualne “rozbudowywanie” tablicy, jeżeli jesteś (będziesz) poza zakresem. Więcej informacji w dokumentacji, np. tu http://www.cplusplus.com/reference/vector/vector/resize/

Na razie tylko myślę,

Błąd: aż, a nie tylko

Spróbuj spałować to fastIO. Może to wystarczy do czasu 0.00. Z pozostałymi punktami nie męcz się jeżeli nie jest to konieczne.

Możesz też poszukać inspiracji do tego (i nie tylko tego) zadania na blogu, od którego zaczynałem poznawać świat algoprogramistyczny (z pomocą ludzi, z których jedna już wypowiedziała się w tym temacie): http://zadania-algorytmiczne.blogspot.com/2013/08/2217-statystyka-pozycyjna-kc022.html

EDIT
Na prośbę (priv) @kamfeth zrobiłem to zadanie z czasem 0.00. FastIO jednak odradzam - nie za wiele daje, no chyba że pracy