Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Galaz{
- int nr_panstwa = 0;
- int wspolczynnik = 0;
- };
- int przesiewaj_w_gore(Galaz *Drzewo, int i, int ilosc_zmian_dok){
- int pomocniczaP = 0;
- int pomocniczaP2 = 0;
- while(1){
- if(Drzewo[i].wspolczynnik > Drzewo[(i-1)/2].wspolczynnik && (i-1) >= 0 ){
- pomocniczaP = Drzewo[(i-1)/2].wspolczynnik;
- pomocniczaP2 = Drzewo[(i-1)/2].nr_panstwa;
- Drzewo[(i-1)/2].wspolczynnik = Drzewo[i].wspolczynnik;
- Drzewo[(i-1)/2].nr_panstwa = Drzewo[i].nr_panstwa;
- Drzewo[i].wspolczynnik = pomocniczaP;
- Drzewo[i].nr_panstwa = pomocniczaP2;
- i = (i-1)/2;
- ++ilosc_zmian_dok;
- }
- else{
- break;
- }
- }
- return ilosc_zmian_dok;
- }
- int przesiewaj_w_dol(Galaz *Drzewo, int i,int liczba_panstw, int ilosc_zmian_dok){
- int pomocniczaP = 0;
- int pomocniczaP2 = 0;
- while((2*i)+2 < liczba_panstw){
- if(Drzewo[(2*i)+1].wspolczynnik < Drzewo[(2*i)+2].wspolczynnik){
- pomocniczaP = Drzewo[(2*i)+2].wspolczynnik;
- pomocniczaP2 = Drzewo[(2*i)+2].nr_panstwa;
- Drzewo[(2*i)+2].wspolczynnik = Drzewo[i].wspolczynnik;
- Drzewo[(2*i)+2].nr_panstwa = Drzewo[i].nr_panstwa;
- Drzewo[i].wspolczynnik = pomocniczaP;
- Drzewo[i].nr_panstwa = pomocniczaP2;
- i = (2*i)+2;
- ++ilosc_zmian_dok;
- }
- else if(Drzewo[(2*i)+1].wspolczynnik >= Drzewo[(2*i)+2].wspolczynnik){
- pomocniczaP = Drzewo[(2*i)+1].wspolczynnik;
- pomocniczaP2 = Drzewo[(2*i)+1].nr_panstwa;
- Drzewo[(2*i)+1].wspolczynnik = Drzewo[i].wspolczynnik;
- Drzewo[(2*i)+1].nr_panstwa = Drzewo[i].nr_panstwa;
- Drzewo[i].wspolczynnik = pomocniczaP;
- Drzewo[i].nr_panstwa = pomocniczaP2;
- i = (2*i)+1;
- ++ilosc_zmian_dok;
- }
- }
- while(1){
- if( ((2*i)+1) < liczba_panstw){
- pomocniczaP = Drzewo[(2*i)+1].wspolczynnik;
- pomocniczaP2 = Drzewo[(2*i)+1].nr_panstwa;
- Drzewo[(2*i)+1].wspolczynnik = Drzewo[i].wspolczynnik;
- Drzewo[(2*i)+1].nr_panstwa = Drzewo[i].nr_panstwa;
- Drzewo[i].wspolczynnik = pomocniczaP;
- Drzewo[i].nr_panstwa = pomocniczaP2;
- ++ilosc_zmian_dok;
- }
- break;
- }
- return ilosc_zmian_dok;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- int liczba_panstw, ilosc_zmian;
- cin >> liczba_panstw;
- Galaz * Drzewo = new Galaz[liczba_panstw];
- for(int i = 0; i < liczba_panstw; ++i){
- cin >> Drzewo[i].nr_panstwa;
- cin >> Drzewo[i].wspolczynnik;
- }
- cin >> ilosc_zmian;
- int wczytywany_nr;
- int wczytywany_wspolczynnik;
- int ilosc_zmian_dok = 0;
- for(int j = 0; j < ilosc_zmian; ++j){
- cin >> wczytywany_nr;
- cin >> wczytywany_wspolczynnik;
- int pomocnicza = 0;
- int i = 0;
- while(1){
- if(wczytywany_nr != Drzewo[i].nr_panstwa){
- ++i;
- }
- else{
- pomocnicza = Drzewo[i].wspolczynnik;
- Drzewo[i].wspolczynnik = wczytywany_wspolczynnik;
- break;
- }
- }
- if(Drzewo[i].wspolczynnik > pomocnicza){
- ilosc_zmian_dok = przesiewaj_w_gore(Drzewo, i, ilosc_zmian_dok);
- }
- else if(Drzewo[i].wspolczynnik < pomocnicza){
- ilosc_zmian_dok = przesiewaj_w_dol(Drzewo, i, liczba_panstw, ilosc_zmian_dok);
- }
- i = 0;
- }
- //for(int k = 0; k < liczba_panstw; ++k){
- //cout << endl;
- //cout << Drzewo[k].nr_panstwa << ' ' << Drzewo[k].wspolczynnik;
- //cout << endl;
- //}
- cout << endl << ilosc_zmian_dok;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement