12231. Kolejka [AL_01_02]

Cześć Wam,

Mam trochę inny problem. Sędzia odrzuca mi kod prawdopodobnie ze względu na wyciek pamięci.
Nie potrafię go zlokalizować. Może jakieś wprawne oko mi podpowie. Z góry dzięki

#include<cstdlib>
#include<iostream>  
#include <cstdio>
#include <cstring>
using namespace std;

string z;
int dl;
int tab[100];

void sortowanie(int *tab, int n)
{
  for (int i=1; i<dl; i++)
{
    for (int j=dl-1; j>=1; j--)
    {
        if (tab[j]>tab[j-1])
        {
            int bufor;
            bufor=tab[j-1];
            bufor=0;
            tab[j-1]=tab[j];
            tab[j]=bufor;
        }
    }
}
}


int main()
{
    int prob;
    cin>>prob;

for(int j=1; j<=prob; j++)
{
    cin>>z;
    dl=z.length();


    for (int i=0; i<dl; i++)
    {

        tab[i]=(int)z[i];

    }
    sortowanie(tab,dl);


    for(int i=0; i<dl; i++)
    {
        if(tab[i+1]==0)
        {
            dl=(i);
        }
        cout<<(char)tab[i];
    }

    delete[] tab;


}
return 0;
}

Może źle widzę , ale na mój gust to zwalniasz pamięć, której nie zaalokowałeś

Po usunięciu delete [] tab; nic się nie zmieniło

Dokładnie, tab jest globalną, statyczną tablicą, więc nigdzie nie wycieknie, a zwalnianien jej [delete] jest błędem.

n < 10^6 i jednocześnie t*n < 10^7 więc gdy t = 10, to n może być <= 10^6

n = 100 to stanowczo za mało.

Dodatkowo nie sprawdzałem, ale Ty powinieneś potestować, czy napewno twój sposób jest poprawny. Sortowanie tutaj raczej nie jest potrzebne a nawet powiedziałbym, że jest tu błędem.

No dobra, naniosłem kilka poprawek. Teraz wyskakuje, że przekroczono limit czasu. No nic. trzeba to przyspieszyć. Pomyślę nad rezygnacją z sortowania, by chyba to przez to.

  #include<cstdlib>
  #include<iostream>
  #include <cstdio>
  #include <cstring>
  using namespace std;

 string z;
 int dl;
 int tab[1000000];

void sortowanie(int *tab, int n)
{
 for (int i=1; i<dl; i++)
{
    for (int j=dl-1; j>=1; j--)
    {
        if (tab[j]>tab[j-1])
        {
            int bufor;
            bufor=tab[j-1];
            bufor=0;
            tab[j-1]=tab[j];
            tab[j]=bufor;
        }
    }
 }
}


int main()
{
int prob;
cin>>prob;

for(int j=1; j<=prob; j++)
{
    cin>>z;
    dl=z.length();

 if (prob>=1000000 ||dl>1000000 || (prob*dl)>10000000 ) break;
    for (int i=0; i<dl; i++)
      {

          tab[i]=(int)z[i];

    }
    sortowanie(tab,dl);


    for(int i=0; i<dl; i++)
    {
        if(tab[i+1]==0)
        {
            dl=(i);
        }
        cout<<(char)tab[i];
    }

}
return 0;
}

Jeżeli to jest ta jedna z tych twoich poprawek, to muszę Ci powiedzieć, że jest zupełnie bez sensu. Jej usunięcie oczywiście też nic nie zmieni.

Jeżeli nazywasz funkcję sortowanie, to inni mogą uwieżyć, że tak faktycznie jest i bez zagłębiania się w twój kod, stwierdzić, że sortowanie jest tu zupełnie bez sensu. Może lepiej nazwać tą funkcję np kasowanie_sortowanie(…) - ale dalej to nic nie zmieni.

Jeszcze jest parę błędóœ, ale nie będę ich Ci wytykał, bo jeszcze uwierzysz, że wystarczy tylko je poprawić i już. Nie nie wystarczy.

To zadanie jest w kateorii średnie, więc może powinieneś zacząć od kategorii łatwe lub https://pl.spoj.com/PDSTPROG/4, ale oczywiście to twoja decyzja.

Albo kolejkowanie - chodzi mi tylko o poprawienie czytelności.

Próbowałem przyśpieszyć i już skończyły mi się pomysły.
Co jeszcze można by zrobić by kod był wystarczająco szybki?

Bardzo proszę o podpowiedź co w moim kodzie jest na tyle wolne, że nie przechodzi on i dostaję przekroczony limit czasu.
https://ideone.com/FvdyxU25

W programie na ideone jest krutki test, ktory nie ma znaku konca lini na koncu. Jest to sytuacja raczej prawidlowa. Program nie obsluguje takiej sytuacji(nie obsluguje EOF). Reszta wydaje sie prawidlowa, ale sam tego zadania nie zrobilem.

Jakby ktos mial jeszcze problem, zamiast pisac cout nalezy pisac printf itd. sam sie meczylem tyle czasu, pisalem program na rozne sposoby a rozwiazanie prozaiczne