Zadanie SPOJ PP0506A - Sort 1

Question

Link do Zadania http://pl.spoj.com/problems/PP0506A/

Zadanie przechodzi wszystkie możliwe ekstremalne testy a sędzia nie akceptuje i cały czas dostaję "Błędna odpowiedź" Tracę już nerwy i cierpliwość. Może ktoś rzucić okiem o co chodzi sędziemu?

#include <iostream>

using namespace std;

class tabela
{
public:
    string napis;
    int x,y,odleglosc;
};

void wczytaj(tabela *tab, int liczby);
void quicksort(tabela *tab, int lewy, int prawy);


int t;   //liczba testów
int ile; //liczba współrzędnych

int main()
{
ios_base::sync_with_stdio(0);
cin>>t;
while (t--) {
    ios_base::sync_with_stdio(0);
    cin >> ile;
    tabela * tab;
    tab = new tabela [ile+1];
    wczytaj(tab,ile);
    quicksort(tab,0,ile-1);

    for (int i=0; i<ile; i++) {
        cout << tab[i].napis << " " << tab[i].x << " "<< tab[i].y;
        if (i!=ile-1) {
            cout << endl;
        }
    }
    cout << endl << endl;
    delete [] tab;
}
    return 0;
}

void wczytaj(tabela *tab, int liczby) {

    int a,b;
    string nazwa;
        for (int i=0; i<liczby; i++) {
            cin >> nazwa >> a >> b;
            tab[i].napis = nazwa;
            tab[i].x = a;
            tab[i].y = b;
            tab[i].odleglosc = (a*a+b*b);
        }
     }

void quicksort(tabela *tab, int lewy, int prawy) {
    int v=(lewy+prawy)/2;
    int i,j;
    i=lewy;
    j=prawy;
    do
    {
        while(tab[i].odleglosc<tab[v].odleglosc) i++;
        while(tab[j].odleglosc>tab[v].odleglosc) j--;
        if(i<=j)
        {
            tab[ile]=tab[i];
            tab[i]=tab[j];
            tab[j]=tab[ile];
            i++;
            j--;
        }
    }
    while(i<=j);
    if(j>lewy) quicksort(tab,lewy, j);
    if(i<prawy) quicksort(tab, i, prawy);
}

 

Comments

1. Doprowadź ten kod do ładu. 

- Nic nie wnoszące komentarze do zmiennych. Nazywaj zmienne tak, aby nie trzeba było komentować co oznaczają.

- ios_base::sync_with_stdio(0) - to jest zupełnie niepotrzebne(z tego co mi wiadomo, może masz jakiś powód żeby używać tego), zaśmieca tylko kod.

- wyeliminuj zmienne globalne

2. Tak na przyszłość stosuj nazwy rzeczywiście odzwierciedlające dane, które zmienne przechowują. Pole "odleglosc" nie przechowuje odleglosci.

3. Prawdopodobnie wyniki masz dobrze, tylko wypisujesz jakieś bezsensowne końce linii.

Linijka 37: 

cout << endl << endl;

Linijka 33: 

if (i!=ile-1) {
    cout << endl;
}

Po co to jest?

---

Dziękuję za uwagi, jednak mimo wszystko nie mają one wpływu na zaliczenia zadania. Problem leży w funkcji quicksort. Przeanalizuje jeszcze ją raz dokładnie.

- ios_base::sync_with_stdio(0) zastosowałem ponieważ komuś właśnie to pomogło w tym zadaniu.

"Pole "odleglosc" nie przechowuje odleglosci." Tak zgadza się jednak wcześniej to dokładnie była odległość ale dla optymalizacji wyrzuciłem wyciągania pierwiastka z odległości. A nazwa pozostała.

"Prawdopodobnie wyniki masz dobrze, tylko wypisujesz jakieś bezsensowne końce linii."

Tu to samo. Mnóstwo osób w tym zadaniu miała problem z brakiem tych endlajnów. W treści jest napisane aby oddzielać kolejne testy pustą linią. Tak więc jak wszystko działa a sędzia nie zalicza to szuka się już wszystkich możliwych przyczyn. Dlatego kombinowałem z róznymi ustawieniami endlinów - po inputach po outputach itp...

Answer 1

Nie wiem czy ma to jakieś znaczenie, ale gdy wpiszę:
1
3
A 0 0
B 0 0
C 3 3
To na wyjściu dostaję:
B 0 0
A 0 0
C 3 3
Możliwe, że powinna być kolejność A, B ,C.
W każdym razie poprawiłem troszeczkę twój kod:
1. Usunąłem dodatkową przerwę między testami.
2. Usunąłem funkcję Quicksort i zastosowałem wbudowany algorytm sortujący w c++ (wymaga on operatora < w klasie, tak więc go również dopisałem)
Ten kod działa i jest przyjmowany przez SPOJ'a:
http://cpp.sh/3xfg

Comments

Dzięki zaraz obczaję co usprawniłeś.

W tekście jet napisane że nie ma takiej pary współrzędnych która ma taką samą odległość więc punkty A 0 0 oraz B 0 0 nie są testowane. Dlatego też wyklucza to raczej winę quicksorta.

---

Sprawdziłem różne warianty i wina leży tylko i wyłącznie w quicksorcie.

Dziękuję za pomoc. Aczkolwiek i tak nie wiem dlaczego sortowania quicksortem nie przyjmuje.