bathory0xff Temat założony przez niniejszego użytkownika |
[C++] "syscalls limit exceeded" - Przekroczenie limitu czasowego » 2015-11-02 00:13:02 Witam, mam problem z zadaniem na stronie Main 2. Jest to akcelerator. W zadaniu należy znaleźć i wypisać odpowiednie wartości za pomocą wyszukiwania binarnego ( http://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/akc/). Program działa poprawnie, zoptymalizowałem go tak, by liczył wszystko jak najszybciej, jednak mam problem nie z obliczeniami a ze zwykłym wypisaniem. Kod: #include <iostream>
using namespace std;
int najw( int t[], int n, int a ) {
int k = n - 1, p = 0, s;
while( p < k ) {
s =( p + k + 1 ) / 2;
if( t[ s ] <= a )
p = s;
else
k = s - 1;
}
if( t[ k ] == a )
return k + 1;
else
return 0;
}
int najm( int t[], int n, int a ) {
int k = n - 1, p = 0, s;
while( p < k ) {
s =( k + p - 1 ) / 2;
if( t[ s ] >= a )
k = s;
else
p = s + 1;
}
if( t[ p ] == a )
return p + 1;
else
return 0;
}
int main() {
int n, m;
cin >> n;
int t[ n ];
for( int i = 0; i < n; i++ )
cin >> t[ i ];
cin >> m;
int u[ m ];
for( int i = 0; i < m; i++ ) {
cin >> u[ i ];
int x = najw( t, n, u[ i ] );
if( x == 0 )
cout << 0 << endl;
else {
int y = najm( t, n, u[ i ] );
cout << x - y + 1 << endl;
}
}
return 0;
} Cały problem polega na tym, że dla ostatniego zestawu testowego wyskakuje komunikat "Przekroczenie limitu czasowego" (1.41s/2.00s), zaś opis błędu to " syscalls limit exceeded". Próbowałem wysłać kod, który nie wykonuje żadnych obliczeń i dla każdego wpisywanego zestawu wypisuje po prostu jedynkę. Efekt był ten sam, z tym że czas wynosił 1.34/2.00. Dla każdego innego zestawu danych moje odpowiedzi są poprawne, problem występuje tylko w tym ostatnim. Co powinienem zmienić w kodzie aby otrzymać pozytywny wynik testów? |
|
j23 |
» 2015-11-02 11:13:56 Trochę czepialstwa: cin >> n;
int t[ n ];
...
cin >> m;
int u[ m ]; |
W C++ takie tablice (VLA) to błąd, kod nie powinien się skompilować. Sensu tablicy 'u' nie widzę. Co do błędu. Daj na końcu programu 'cout.flush();'. |
|
bathory0xff Temat założony przez niniejszego użytkownika |
» 2015-11-02 12:51:46 Rozumiem, że użycie tablicy 'u' nie ma większego sensu. Po prostu próbowałem wpisywać dane na różne sposoby. Wpisanie tablicą nic nie zmieniło, będę wpisywał za pomocą inta. Użycie funkcji flush nie pomogło. Dalej wyskakuje ten sam komunikat. Mam natomiast pytanie. Co jest złego w deklarowaniu tablicy z określoną ilością miejsc? I co mogę zrobić z tym komunikatem? |
|
j23 |
» 2015-11-02 14:21:47 Jeśli chodzi o tablice, to sprawa prosta - VLA w standardowym C++ nie istnieje. Kompilator powinien zgłosić błąd składniowy przy próbie kompilacji. Nie wiem, jak nowe wersje g++, ale te wcześniejsze domyślnie dopuszczały taką konstrukcję. VLA to element języka C (od C'99).
Co do komunikatu, trudno powiedzieć, co może być problemem. Pierwsze co mi się nasunęło to te flushowanie strumienia wyjściowego. |
|
darko202 |
» 2015-11-02 15:22:06 1. przeczytaj jeszcze raz wskazówkę do zadania Wskazówki Nie próbuj przy kazdym zapytaniu przejezdzac petla przez wszystkie odczyty, jest to bowiem zbyt czasochłonne i prawie na pewno spowoduje komunikat Przekroczenie limitu czasu. Dobrym pomysłem na pierwszy krok jest znalezienie szukanej liczby w tablicy za pomoca wyszukiwania binarnego. Nie powinienes jednak potem iterowac sie po elementach tablicy, szukajac wszystkich wystapien tej liczby – znowu, to równiez spowoduje, ze Twój program bedzie działał zbyt długo. Pamietaj, ze w algorytmice zwykle zakłada sie, ze Twój program dostanie nieprzyjemne dane wejsciowe — postaralismy sie zatem o mozliwie trudne testy! 2. przeczytaj treść zadania ... Z braku lepszych zajec ustawił wszystkie wyniki pomiarów w kolejnosci niemalejacej. ... 3. wyszukiwanie binarne przeczytaj np. http://www.algorytm.edu.pl/algorytmy-maturalne/wyszukiwanie-binarne.html4. porównaj algorytm z p3 z Twoim to nie jest chyba ww. algorytm. podsumowując: przypuszczam że jak uważnie wykonasz wszystkie ww. kroki to znajdziesz rozwiązanie problemu powodzenia :) |
|
bathory0xff Temat założony przez niniejszego użytkownika |
» 2015-11-02 16:47:01 "Próbowałem wysłać kod, który nie wykonuje żadnych obliczeń i dla każdego wpisywanego zestawu wypisuje po prostu jedynkę. Efekt był ten sam, z tym że czas wynosił 1.34/2.00."
Hmmm. Dobra, jeszcze raz określę swój problem. Nie mam problemu ze znalezieniem tych liczb tylko z WYPISANIEM ich w konsoli. W programie, który dla każdego zestawu wypisuje '1' opisany przeze mnie problem dalej WYSTĘPUJE. Chciałem się więc dowiedzieć co zrobić, aby wpisywanie i wypisywanie (znajdowanie wyników nie ma tu znaczenia) działało poprawnie dla tego miliona linii określonego w zadaniu.
I co do odesłania mnie do algorytmu...
Dokładnie przeczytałem wskazówkę i zastosowałem się. Dla każdego pozostałego zestawu mam poprawny wynik. Przekształciłem po prostu algorytm tak, aby znaleźć pierwsze i ostatnie wystąpienie szukanej wartości i zwrócić ich pozycję w ciągu do funkcji głównej (np. dla tabeli o numerze 0 program zwróci 1, a jeżeli nie znajdzie żadnego wystąpienia zwróci 0). Ta część programu działa poprawnie. Chcę po prostu wiedzieć co może oznaczać "syscalls limit exceeded" i co mam zmienić żeby program wreszcie zaliczył test. |
|
przemek5332 |
Rozwiązanie » 2017-03-02 20:54:03 Odkopuję :-)
Też miałem ten problem i szukając rozwiązania w google ten temat wyświetlił mi się jako pierwszy.
Z nieznanych mi przyczyn problemem jest użycie cin i cout, po przepisaniu programu na printf i scanf sprawdzarka przyznała mi punkty.
Mam nadzieję że komuś pomogę. |
|
carlosmay |
» 2017-03-02 21:47:51 Zawsze w C++ możesz skorzystać z sync_with_stdio dla standardowego strumienia. |
|
| « 1 » 2 |