Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów. Postanowiłem więc skorzystać z funkcji getchar_unlocked(), która rzekomo znajduje się w bibliotece stdio.h
Kompilator wyświetla błąd, że jest ona niezdefiniowana.
0
0
getchar_unlocked() nie jest funkcją standardową, więc może jej nie być w ogóle w Twoim środowisku. Jeśli to istotny problem, to napisz prostego ifdefa, który zamieni wywołanie getchar na getchar_unlocked na spoju.
0
Roman Kwaśniewski napisał(a):
Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów.
Zakładam, że wpadłeś w "urban legend" na temat słabej szybkości strumieni C++.
To jest fikcja. Kiedyś ktoś pokazywał testy, że dobrze użyte strumienie C++ są szybsze od printf.
Jak korzystasz ze strumieni na SPOJ to jest kilka prostych zasad: Wymuszanie wysokiej wydajności iostream
Daj linka do zadania, żebyśmy wiedzieli, że faktycznie wąskim gardłem są operacje IO.
0
To wszystko oczywiście zawsze dodaję. Mało zadań wchodzi na 100 "gołymi" strumieniami, ale co mam zrobić jeśli mimo wszystko program wchodzi na 99. Tylko raz w życiu miałem taki problem ( wtedy była uszkodzona paczka ) Tym razem raczej tak nie jest sądząc po tym, że sporo osób wbiło to na 100.
0
@Roman Kwaśniewski: ja zrobiłem dużo zadań ze spoja, ale cin/cout prawie nigdy nie robiły mi problemów - tylko w przypadku gdy masz b. dużo danych wejściowych, a takich zadań jest dość mało.
Zawsze dodawaj ios_base::sync_with_stdio(false); na początku maina. Ale jeszcze nie miałem zadania żeby mi scanf/print nie wystarczył.
Daj przykładowe zadanie z Twoim rozwiązaniem to damy Ci wskazówki co zmienić żeby przeszło (zakładając że masz poprawne optymalne rozwiązanie - jeśli nie to możemy Cię nakierować żeby nie psuć Ci zabawy)
0
Zadanie jest rozwiązane liniowo. Ponieważ danych też jest liniowo dużo to rozwiązanie jest optymalne. Poza tym program dostaje 99 czyli prawie maksa. Właściwie to w żadnym teście nie ma przekroczenia limitu czasu. Mam tylko odjęte punkty za czas nie-wzorcowy.
0
kq napisał(a):
getchar_unlocked()nie jest funkcją standardową, więc może jej nie być w ogóle w Twoim środowisku. Jeśli to istotny problem, to napisz prostego ifdefa, który zamieni wywołaniegetcharnagetchar_unlockedna spoju.
POSIX je definiuje. Jednak może być potrzebne zdefiniowanie feature test macros dla nich (jak to się po polsku nazywa?) - te są w Twojej gestii i / lub odp flagi kompilatora - tymi zarządza oczywiście sędzia.
Dokumentacja, która o tym mówi (dla Linuxa): https://linux.die.net/man/3/getchar_unlocked
Na SPOJ próbowałem (w C, nie w C++, ale chyba powinno być tak samo) i działało jeśli przed #include <stdio.h> dałem #define _POSIX_SOURCE. Czyli:
#define _POSIX_SOURCE
#include <stdio.h>
// dalej kod
(jeśli u Cb to nie SPOJ to oczywiście nie gwarantuję, że zadziała, ale warto spróbować IMO)
MarekR22 napisał(a):
Roman Kwaśniewski napisał(a):
Pomimo przepisania mojego programu na printf-y wchodzi on na 99 punktów.
Zakładam, że wpadłeś w "urban legend" na temat słabej szybkości strumieni C++.
To jest fikcja. Kiedyś ktoś pokazywał testy, że dobrze użyte strumienie C++ są szybsze od printf.Jak korzystasz ze strumieni na SPOJ to jest kilka prostych zasad: Wymuszanie wysokiej wydajności iostream
Zgadza się niemniej getchar_unlocked jest szybszy (chociaż bardziej upierdliwy w obsłudze) zarówno od stdio jak i od strumieni. Są zadania, przy których ich użycie jest jedynym mi znanym sposobem na zdobycie najszybszego możliwego czasu, aczkolwiek nie znam zadania, w których byłoby to warunkiem zdobycia maks punktów (co nie znaczy, że takie nie istnieje - w sumie sumarycznie mało zadań znam).
Roman Kwaśniewski napisał(a):
sporo osób wbiło to na 100.
Może to świadczyć, że jednak da się wbić na 100 bez getchar_unlocked.
Roman Kwaśniewski napisał(a):
Zadanie jest rozwiązane liniowo. Ponieważ danych też jest liniowo dużo to rozwiązanie jest optymalne.
Niekoniecznie. Stała się liczy w takich zadaniach. Złożoność asymptotyczna zresztą w ogóle ma niekiedy znaczenie teoretyczne, bywa tak że teoretycznie lepszy asymptotycznie algorytm ma tak ogromną stałą, że w praktyce jest wolniejszy, niż algorytm o teoretycznie gorszej złożoności. Nie sądzę, by u Cb miało to miejsce, ALE! to pokazuje tylko, jakie czasami znaczenie ma walka o stałą. Zresztą zamiana strumieni czy scanf na getchar_unlocked też ma znaczenie w kwestii stałej tylko. Bottom line: Twój kod może i jest liniowy, niemniej może być nieefektywny. EDIT: Co można zweryfikować, jeśli doczekamy się linka do zadania i Twojego kodu :)
0
Już nie musicie mi pomagać przekroczyłem limit zgłoszeń :)
0
Nie chce mi się wierzyć, że czytanie znak po znaku za pomocą getchar_unlocked będzie szybsze niż czytanie blokami danych (tak zrobi to STL).
Nie uwierzę jeśli ktoś nie zrobi jakiś testów.