Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] "syscalls limit exceeded" - Przekroczenie limitu czasowego

Ostatnio zmodyfikowano 2018-05-29 19:25
Autor Wiadomość
arciobus
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:

C/C++
#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?
P-139498
j23
» 2015-11-02 11:13:56
Trochę czepialstwa:
C/C++
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();'.
P-139506
arciobus
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?
P-139510
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.
P-139517
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.html

4.
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 :)  

P-139519
arciobus
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.
P-139521
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ę.
P-158463
carlosmay
» 2017-03-02 21:47:51
Zawsze w C++ możesz skorzystać z sync_with_stdio dla standardowego strumienia.
P-158465
« 1 » 2
  Strona 1 z 2 Następna strona