[PJWSTK] ASD – wiosna 2015 – Zadanie 5 – Rozwiązanie

TO JEST KOMENTARZ DO ZADANIA ‚PROJEKT 1’ (teraz zwanego Zadanie 5) – http://skalski.at/2013/01/27/pjwstk-asd-projekt-1-rozwiazanie/

W tym kodzie zmieniłem nazwy zmiennych na ‚opisowe’ i dodałem dużo komentarzy przy if’ach i pętlach. Samo działanie/algorytm bez zmian.

Do zrozumienia algorytmu trzeba wiedzieć co to są grafy (tutaj zaimplementowane jako tablice i listy).

Co do dużej ilości klas:

ListElementTown, ListTowns, ListElementThief, ListThiefs – to moje własne implementacje ‚list’, równie dobrze do testów możecie użyć normalnej C++’owej listy http://www.cplusplus.com/reference/vector/vector/ (ma ona więcej funkcjonalości i jest znacznie wolniejsza, więc walcząc o sekundy i tak warto pomyśleć o własnym ‚list’ i ‚map’ [dla ‚optymalizacja hardcore’owa])

Opis ogólny założeń programu:
kandydat – obiekt ktory liczy koszt kampani A/B i zajmuje miasta [tworzy sztaby wyborcze]
miasto – wierzcholek grafu, zawierajacego informacje o sasiedztwie z innymi miastami
sztab wyborczy – przypisanie danego miasta do kandydata, przypisanego miasta nie moze przejac inny kandydat
prawybory – jezeli w miescie nie ma jeszcze ‚sztabu wyborczego’, a w ktoryms z miast sasiadujacych jest, to w danym miescie nalezy przeprowadzic prawybory zgodnie z podanym algorytmem (wygrywa ten kandydat ktorego sztaby sa w najwiekszej ilosci miast sasiednich)
tura – jeden obrot petli w ktorym kazde miasto w ktorym jest sztab proboje zalozyc sztab (doprowadza do prawyborow wpisujac swojego kandydata na liste) w sasiednich miastach

KANDYDACI JAKO WIRUSY:
Program mozna latwiej zrozumiec, patrzac na problem jak na komorki organizmu (miasta) i wirusy (kandydatow):
Wirusy znalazly sie w kilku komorkach, kazda komorka zarazona w danej ‚turze’ zaraza wszystkie z ktorymi ma kontakt [miasta sasiedzkie] w nastepnej turze
Tak wiec mozna podzielic komorki na 3 grupy:
– nie zarazone
– zarażone
– zarażające
1. Kazda komorka w chwili zarazenia staje sie zarazajaca [w nastepnej turze!]
2. Kazda komorka po turze w ktorej zarazala staje sie ‚zarazona’ [sama juz wiecej nie zaraza, nie ma po co, bo wszystkich sasiadow juz zarazila, a sasiadow nie przybywa]

Dana nie zarazona komorka, moze byc w danej turze zarazana przez wiecej, niz jedna sasiednia komorke, wygrywa ten wirus ktory ma najwiecej sasiadujacyh zarazonych komorek [przy remisie porownujemy ID wirusa wedlug polecenia w wersji A i B].
W zalozeniu kazda komorka ma jakiegos sasiada, wiec algorytm mieli dane do czasu, az ilosc zarazonych komorek jest rowna liczbie wszystkich komorek.

UWAGA! Opisany powyżej algorytm to teoretycznie najwydajniejsza wersja kodu, a nie ta jaka jest przedstawiona w C++ [zarażone ciągle zarażają.., dużo rzeczy jest zapisywane do tymczasowych list mimo, że mogło by działać bez nich itd.].

Kod C++ był pisany na ostatnią chwilę, a przed publikacją przeszedł jeszcze obróbkę po której zgodność z oryginałem według ‚plagiatora’ wynosiła poniżej 5% [poprzez dodanie mniej wydajnych pętli, ‚get’ w listach, deklaracje zmiennych w złych miejscach itd.]

ROZWIĄZANIE KTÓRE OPUBLIKOWAŁEM W C++ JEST DALEKIE OD TEORETYCZNIE NAJSZYBSZEGO. W DODATKU NIE JEST WYDAJNE (CO ZMIENIĆ OPISZĘ NA KOŃCU POSTA). Nie można wprost powiedzieć jakie rozwiązanie będzie najlepsze, bo na każdy algorytm duży wpływ ma ilość miast, kandydatów i połączeń między miastami, a jakie są ilości w danych testowych to nie wiem 🙁

#include<stdio.h>
 
class Miasto;
class Kandydat;
 
class ListElementTown
{
    public:
        Miasto* miasto;
        ListElementTown* nastepnyElementListy;
 
        ListElementTown(Miasto* m)
        {
            this->miasto = m;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementTown(Miasto* m, ListElementTown* nastepnyElementListy)
        {
            this->miasto = m;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListTowns
{
    public:
        ListElementTown* pierwszyElementListy;
        int iloscElementow;
 
        ListTowns()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Miasto* get(int elementIterator)
        {
            ListElementTown* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->miasto;
        }
 
        void add(Miasto* m)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementTown(m);
            else
                pierwszyElementListy = new ListElementTown(m, pierwszyElementListy);
 
            iloscElementow++;
        }
 
        bool contains(Miasto* m)
        {
            ListElementTown* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(m == tmp->miasto)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
 
class ListElementThief
{
    public:
        Kandydat* kandydat;
        ListElementThief* nastepnyElementListy;
 
        ListElementThief(Kandydat* t)
        {
            this->kandydat = t;
            this->nastepnyElementListy = NULL;
        }
 
        ListElementThief(Kandydat* t, ListElementThief* nastepnyElementListy)
        {
            this->kandydat = t;
            this->nastepnyElementListy = nastepnyElementListy;
        }
};
 
class ListThiefs
{
    public:
        ListElementThief* pierwszyElementListy;
        int iloscElementow;
 
        ListThiefs()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
 
        Kandydat* get(int elementIterator)
        {
            ListElementThief* tmp = pierwszyElementListy;
            for(int i = 0; i < elementIterator; i++)
                tmp = tmp->nastepnyElementListy;
 
            return tmp->kandydat;
        }
 
        void add(Kandydat* t)
        {
            if(this->pierwszyElementListy == NULL)
                this->pierwszyElementListy = new ListElementThief(t);
            else
            {
                pierwszyElementListy = new ListElementThief(t, pierwszyElementListy);
            }
            iloscElementow++;
        }
 
        bool contains(Kandydat* t)
        {
            ListElementThief* tmp = pierwszyElementListy;
            while(tmp)
            {
                if(t == tmp->kandydat)
                    return true;
 
                tmp = tmp->nastepnyElementListy;
            }
            return false;
        }
 
        void clear()
        {
            pierwszyElementListy = NULL;
            iloscElementow = 0;
        }
};
class Miasto
{
    public:
        int id;
        Kandydat* kandydatKtoryZalozylSztabWyborczyA;
        Kandydat* kandydatKtoryZalozylSztabWyborczyB;
        Kandydat* zwyciezcaA;
        Kandydat* zwyciezcaB;
        ListThiefs* kandydaciA;
        ListThiefs* kandydaciB;
        ListTowns* miastaSasiedzkie;
 
        Miasto(int i)
        {
            id = i;
            kandydatKtoryZalozylSztabWyborczyA = NULL;
            kandydatKtoryZalozylSztabWyborczyB = NULL;
            zwyciezcaA = NULL;
            zwyciezcaB = NULL;
            kandydaciA = new ListThiefs();
            kandydaciB = new ListThiefs();
            miastaSasiedzkie = new ListTowns();
        }
};
 
class Kandydat
{
    public:
        int id;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA;
        int tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB;
        int kosztKampaniA;
        int kosztKampaniB;
 
        Kandydat(int indeks)
        {
            this->id = indeks;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
            this->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            this->kosztKampaniA = 0;
            this->kosztKampaniB = 0;
        }
};

int main()
{ 
    int iloscDzialajacychSztabowWyborczychA = 0;
    int iloscDzialajacychSztabowWyborczychB = 0;
    int iloscMiast = 0;
    int iloscKandydatow = 0;
	// wczytujemy ilosc miast
    fscanf(stdin, "%d", &iloscMiast);
	// tworzymy tablice z miastami
    Miasto* miasta[iloscMiast];
    for(int i = 0; i < iloscMiast; i++)
    {
		// uzupelniamy ja pustymi miastami 
        miasta[i] = new Miasto(i);
    }
    int miasto_1;
    int miasto_2;
	// wczytujemy po kolei po 2 id miast ktore sa sasiadami
    fscanf(stdin, "%d", &miasto_1);
    fscanf(stdin, "%d", &miasto_2);
	// lista tych miast konczy sie dwoma id miast -1
    while(miasto_1 != -1 && miasto_2 != -1)
    {
		// graf ma byc nie skierowany, czyli jak sasiad X wie o sasiedzie Y to Y tez musi wiedziec o X
		// dlatego dodajemy informacje o sasiedze do obu miast
        miasta[miasto_1]->miastaSasiedzkie->add(miasta[miasto_2]);
        miasta[miasto_2]->miastaSasiedzkie->add(miasta[miasto_1]);
        fscanf(stdin, "%d", &miasto_1);
        fscanf(stdin, "%d", &miasto_2);
    }
	// wczytujemy ilosc kandydatow
    fscanf(stdin, "%d", &iloscKandydatow);
	// tworzymy tablice z kandydatkami
    Kandydat* kandydaci[iloscKandydatow];
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// uzupelniamy ja kandydatami ktorzy znaja swoje id
        kandydaci[i] = new Kandydat(i);
    }
	// wczytujemy sztaby poczatkowe kandydatow
    int idSztabuStartowegoKandydata;
    for(int i = 0; i < iloscKandydatow; i++)
    {
		// zalozenie jest takie, ze kazdy kandydat ma wlasne miasto,
		// wiec nie trzeba sprawdzac czy aby 2 nie jest naraz w tym samym miescie startowym
        fscanf(stdin, "%d", &idSztabuStartowegoKandydata);
		// dla algorytmu z zasada A i zasada B przypisujemy, ze ten kandydat juz wygral w tym miescie wybory
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyA = kandydaci[i];
		// naliczany koszt kampani wyborczej
        kandydaci[i]->kosztKampaniA++;
		// dodajemy +1 do ilosci dzialajacych sztabow wyborczych
        iloscDzialajacychSztabowWyborczychA++;
		
		// tutaj to samo co wyzej tylko dla algorytmu 'B'
        miasta[idSztabuStartowegoKandydata]->kandydatKtoryZalozylSztabWyborczyB = kandydaci[i];
        kandydaci[i]->kosztKampaniB++;
        iloscDzialajacychSztabowWyborczychB++;
    }
	/*
	teraz dochodzimy do samego mielenia danych:
	w celu szybszych obliczen zrobimy sobie liste pomocnicza 'miastaWktorychTrzebaPrzeprowadzicPrawybory'
	zalozenia:
	mamy milion wierzcholkow grafu [miast]
	kazdy wierzcholek ma polaczenie z tysiacami innych wierzcholkow [innymi miastami]
	mamy kilkuset kandydatow ktorzy maja ustalone miasta startowe
	*/
    ListTowns* miastaWktorychTrzebaPrzeprowadzicPrawybory = new ListTowns();
	// [PĘTLA GŁÓWNA] do poki nie we wszystkich miastach sa sztaby wyborcze
    while(iloscDzialajacychSztabowWyborczychA != iloscMiast && iloscDzialajacychSztabowWyborczychB != iloscMiast)
    {
		// co obrot petli (ture) czyscimy liste pomocnicza
        miastaWktorychTrzebaPrzeprowadzicPrawybory->clear();
		// [PĘTLA 1]
        for(int i = 0; i < iloscMiast; i++)
        {
			// dla kazdego miasta ..
            if(miasta[i]->kandydatKtoryZalozylSztabWyborczyA != NULL && miasta[i]->kandydatKtoryZalozylSztabWyborczyB != NULL)
            {
				// .. w ktorym jest sztab wyborczy [X kandydata]
				// [PĘTLA 1.1]
                for(int i2 = 0; i2 < miasta[i]->miastaSasiedzkie->iloscElementow; i2++)
                {
					// dla kazdego miasta sasiedniego ..
                    if(miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyA == NULL && miasta[i]->miastaSasiedzkie->get(i2)->kandydatKtoryZalozylSztabWyborczyB == NULL)
                    {
						// .. w ktorym nie ma sztabu wyborczego
						
						// wszystko jest w 'ifach', bo wiele innych miast moze byc sasiadem w ktorym jest juz sztab wyborczy,
						// a lista kandydatow i miast w ktorych maja byc wybor ma byc bez powtorzen
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyA)))
                        {
							// dodaj do listy kandydatow A o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciA->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyA);
                        }
                        if(!(miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->contains(miasta[i]->kandydatKtoryZalozylSztabWyborczyB)))
                        {
							// dodaj do listy kandydatow B o ile jeszcze na niej nie jest
                            miasta[i]->miastaSasiedzkie->get(i2)->kandydaciB->add(miasta[i]->kandydatKtoryZalozylSztabWyborczyB);
                        }
                        if(!(miastaWktorychTrzebaPrzeprowadzicPrawybory->contains(miasta[i]->miastaSasiedzkie->get(i2))))
                        {
							// dodaj miasto sasiedzkie do listy miast w ktorych trzeba przeprowadzic prawybory w tej turze
                            miastaWktorychTrzebaPrzeprowadzicPrawybory->add(miasta[i]->miastaSasiedzkie->get(i2));
                        }
                    }
                }
            }
        }
		// koniec 'for' ktory generowal liste miast w ktorych trzeba przeprowadzic prawybory i dodawal w tych miastach kandydatow
        ListElementTown* elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        int loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// teraz trzeba przeprowadzic prawybory i ustalic ktory kandydat wygral w danym miescie
		// przy czym jego wygrana nie moze wplywac na obliczenia innych wygranych (na to moze wplywac dopiero w nastepnej 'turze' algorytmu)
		// dlatego wynik prawyborow zapisujemy do zmiennych 'zwyciezcaA' i 'zwyciezcaB'
		// [PĘTLA 2]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* aktualneMiasto = elementPoczatkowy->miasto;
            Kandydat* tmpKandydat = NULL;
			// z dziwnych powodow trzymamy ilosc 'sztabow wyborczych w miastach sasiednich' w kandydatach,
			// wiec trzeba to co obrot petli czyscic w kazdym kandydacie
            for(int x = 0; x < iloscKandydatow; x++)
            {
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA = 0;
                kandydaci[x]->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB = 0;
            }
            int loopsCounter_2 = aktualneMiasto->miastaSasiedzkie->iloscElementow;
            ListElementTown* petlaPoSasiadach = aktualneMiasto->miastaSasiedzkie->pierwszyElementListy;
			// teraz dodajemy w tych kandydatach liczbe przechowujaca w ilu miastach sasiedzkich [dla 'aktualneMiasto'] jest sztab danego kandydata
            for(int ii = 0; ii < loopsCounter_2; ii++)
            {
                Miasto* tmpMiasto = petlaPoSasiadach->miasto;
                if(tmpMiasto->kandydatKtoryZalozylSztabWyborczyA != NULL)
                {
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA++;
                    tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB++;
                }
                petlaPoSasiadach = petlaPoSasiadach->nastepnyElementListy;
            }
			// teraz sprawdzamy ktory kandydat ma najwiecej sztabow wyborczych w sasiadujacych miastach
            Kandydat* zwyciezcaA = aktualneMiasto->kandydaciA->get(0);
            Kandydat* zwyciezcaB = aktualneMiasto->kandydaciB->get(0);
 
			// dla A
            loopsCounter_2 = aktualneMiasto->kandydaciA->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciA->get(i2);
                if((zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA > tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA) || (zwyciezcaA->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichA && zwyciezcaA->id < tmpKandydat->id))
                    zwyciezcaA = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaA = zwyciezcaA;
            aktualneMiasto->kandydaciA->clear();
			// dla B
            loopsCounter_2 = aktualneMiasto->kandydaciB->iloscElementow;
            for(int i2 = 1; i2 < loopsCounter_2; i2++)
            {
                tmpKandydat = aktualneMiasto->kandydaciB->get(i2);
                if((zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB < tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB) || (zwyciezcaB->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB == tmpKandydat->tymczasowyLicznikIlosciSztabowKandydataWmiastachSasiedzkichB && zwyciezcaB->id > tmpKandydat->id))
                    zwyciezcaB = tmpKandydat;
            }
            aktualneMiasto->zwyciezcaB = zwyciezcaB;
            aktualneMiasto->kandydaciB->clear();
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
        elementPoczatkowy = miastaWktorychTrzebaPrzeprowadzicPrawybory->pierwszyElementListy;
        loopsCounter = miastaWktorychTrzebaPrzeprowadzicPrawybory->iloscElementow;
		// znamy juz zwyciezcow, teraz trzeba ich zwycieztwa w prawyborach przepisac na zalozone sztaby, aby w kolejnej 'turze' mogli zakladac kolejne sztaby
		// [PĘTLA 3]
        for(int i = 0; i < loopsCounter; i++)
        {
            Miasto* tmpMiasto = elementPoczatkowy->miasto;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA = tmpMiasto->zwyciezcaA;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB = tmpMiasto->zwyciezcaB;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyA->kosztKampaniA++;
            tmpMiasto->kandydatKtoryZalozylSztabWyborczyB->kosztKampaniB++;
            iloscDzialajacychSztabowWyborczychA++;
            iloscDzialajacychSztabowWyborczychB++;
            elementPoczatkowy = elementPoczatkowy->nastepnyElementListy;
        }
    }
    for(int i = 0; i < iloscKandydatow; i++)
    {
        fprintf(stdout, "%d %d\n",kandydaci[i]->kosztKampaniA, kandydaci[i]->kosztKampaniB);
    }
    return 0;
}

Optymalizacja:

– zmiana wczytywania danych na szybkie wczytywanie ( http://skalski.at/2014/11/04/asd-spox-spoj-szybkie-wczytywanie-intow-w-c/ )

– przepisanie kodu tak, żeby nigdy nie korzystał z funkcji ‚get’ [super nie wydajna!!] w listach (ZAWSZE algorytm iteruje po elementach listy w pętli od elementu zero do końca, więc zamiast ‚for’ trzeba dać ‚while’ który się zatrzyma jak ‚next’ będzie NULLem)

– jeśli już nie przepisywać kodu na ‚while’ to dodać w listach ‚currentElement’ i ‚currentIndex’, tak, aby po prośbie o element o ‚id’ wyższym o jeden nie jechać pętlą od elementu zerowego do tego o ‚id’ podanych tylko przejść do ‚next’

– w pętlach wiele razy występują np. ‚miasta[i]’ czy jeszcze gorsze ‚miasta[i]->miastaSasiedzkie->get(i2)’, należało by przypisać wartość zmiennej do jakiejś zmiennej tymczasowej Miasto* tmpMiasto i z niej korzystać zamiast w jednej pętli po 8 razy odwoływać się do 2-3 skoków po pamięci RAM

– WSZYSTKIE zmienne tymczasowe powinny być zadeklarowane na początku ‚main’, a nie w jakimkolwiek ‚for’ czy ‚while’, może to zaoszczędzić miliony wrzuceń i usunięć zmiennych z stosu co może dać te brakujące milisekundy do zaliczenia

– w listach funkcja ‚clear’ nie czyści listy, więc jest tutaj duży wyciek pamięci, bo ‚pierwszyElement’ ustawia na NULL, ale ten element mógł wskazywać na listę miliona elementów które już z RAM nie są wywalane, jaki to ma wpływ na wydajność nie wiem [może mieć pozytywny! warto sprawdzić czy aktualna wersja bez czyszczenia nie jest szybsza]

Optymalizacja hardcore’owa:

– kod oznaczony jako PĘTLA 1 i PĘTLA 2 uprościć poprzez nie używanie listy ‚kandydaciA’ (na podstawie której PĘTLA 2 oblicza kto wygrał), tylko użycie mapy ( http://www.cplusplus.com/reference/map/map/)  która by przechowywala danych kandydatow bez powtorzen i ile razy wystapili w miastach sasiedzkich [ pseudokod(!):  std::map<Kandydat* kandydat, int iloscWystapien> kandydaciA ]

Ten wpis został opublikowany w kategorii PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

3 odpowiedzi na „[PJWSTK] ASD – wiosna 2015 – Zadanie 5 – Rozwiązanie

  1. Studenciak pisze:

    Witam,

    Czy mógłby Pan przybliżyć mniej więcej gdzie wprowadzić zmiany w kodzie aby ulepszyć go do sposobu który pan opisał na początku (Dana nie zarazona komorka, moze byc w danej turze zarazana przez wiecej, niz jedna sasiednia komorke…) ?

    • Jerzy Skalski pisze:

      Troche tych zmian bylo, ale rezultat nie powala. Napisalem to tak jak powinno byc [teoretycznie], ale i tak nie przekracza 50 punktów.

  2. mefmund pisze:

    Dla potomnych: dobrym rozwiązaniem jest w klasie miasto dodać jakiegoś boola, ja dodałem „bool wasVoting;” ustawiam go na false w konstruktorze i wtedy w pętli 1 (linie 289 – 293) zastąpiłem czymś takim:
    if(!(miastaSasiedzkie->get(i2)->wasVoting)
    {

    miastaWktorychTrzebaPrzeprowadzicPrawybory->add(miasta[i]->miastaSasiedzkie->get(i2));
    miastaSasiedzkie->get(i2)->wasVoting = true;
    }
    Idea jest taka, że w każdym mieście głosowanie odbywa się tylko raz, więc jeśli sprawdzamy czy nie było tam głosowania to znaczy, że trzeba je przeprowadzić, lista jest czyszczona przed kolejną iteracją więc mamy pewność, że nie będzie więcej głosowań. Zmiana jest na tyle istotna, że pozwoliła skoczyć z 46 punktów na 83.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *