Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.83 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. struct Galaz{
  4. int nr_panstwa = 0;
  5. int wspolczynnik = 0;
  6. };
  7. int przesiewaj_w_gore(Galaz *Drzewo, int i, int ilosc_zmian_dok){
  8. int pomocniczaP = 0;
  9. int pomocniczaP2 = 0;
  10. while(1){
  11. if(Drzewo[i].wspolczynnik > Drzewo[(i-1)/2].wspolczynnik && (i-1) >= 0 ){
  12. pomocniczaP = Drzewo[(i-1)/2].wspolczynnik;
  13. pomocniczaP2 = Drzewo[(i-1)/2].nr_panstwa;
  14. Drzewo[(i-1)/2].wspolczynnik = Drzewo[i].wspolczynnik;
  15. Drzewo[(i-1)/2].nr_panstwa = Drzewo[i].nr_panstwa;
  16. Drzewo[i].wspolczynnik = pomocniczaP;
  17. Drzewo[i].nr_panstwa = pomocniczaP2;
  18. i = (i-1)/2;
  19. ++ilosc_zmian_dok;
  20. }
  21. else{
  22. break;
  23. }
  24. }
  25. return ilosc_zmian_dok;
  26. }
  27. int przesiewaj_w_dol(Galaz *Drzewo, int i,int liczba_panstw, int ilosc_zmian_dok){
  28. int pomocniczaP = 0;
  29. int pomocniczaP2 = 0;
  30. while((2*i)+2 < liczba_panstw){
  31. if(Drzewo[(2*i)+1].wspolczynnik < Drzewo[(2*i)+2].wspolczynnik){
  32. pomocniczaP = Drzewo[(2*i)+2].wspolczynnik;
  33. pomocniczaP2 = Drzewo[(2*i)+2].nr_panstwa;
  34. Drzewo[(2*i)+2].wspolczynnik = Drzewo[i].wspolczynnik;
  35. Drzewo[(2*i)+2].nr_panstwa = Drzewo[i].nr_panstwa;
  36. Drzewo[i].wspolczynnik = pomocniczaP;
  37. Drzewo[i].nr_panstwa = pomocniczaP2;
  38. i = (2*i)+2;
  39. ++ilosc_zmian_dok;
  40. }
  41. else if(Drzewo[(2*i)+1].wspolczynnik >= Drzewo[(2*i)+2].wspolczynnik){
  42. pomocniczaP = Drzewo[(2*i)+1].wspolczynnik;
  43. pomocniczaP2 = Drzewo[(2*i)+1].nr_panstwa;
  44. Drzewo[(2*i)+1].wspolczynnik = Drzewo[i].wspolczynnik;
  45. Drzewo[(2*i)+1].nr_panstwa = Drzewo[i].nr_panstwa;
  46. Drzewo[i].wspolczynnik = pomocniczaP;
  47. Drzewo[i].nr_panstwa = pomocniczaP2;
  48. i = (2*i)+1;
  49. ++ilosc_zmian_dok;
  50. }
  51. }
  52. while(1){
  53. if( ((2*i)+1) < liczba_panstw){
  54. pomocniczaP = Drzewo[(2*i)+1].wspolczynnik;
  55. pomocniczaP2 = Drzewo[(2*i)+1].nr_panstwa;
  56. Drzewo[(2*i)+1].wspolczynnik = Drzewo[i].wspolczynnik;
  57. Drzewo[(2*i)+1].nr_panstwa = Drzewo[i].nr_panstwa;
  58. Drzewo[i].wspolczynnik = pomocniczaP;
  59. Drzewo[i].nr_panstwa = pomocniczaP2;
  60. ++ilosc_zmian_dok;
  61. }
  62. break;
  63. }
  64. return ilosc_zmian_dok;
  65. }
  66. int main() {
  67. ios_base::sync_with_stdio(false);
  68. int liczba_panstw, ilosc_zmian;
  69. cin >> liczba_panstw;
  70. Galaz * Drzewo = new Galaz[liczba_panstw];
  71. for(int i = 0; i < liczba_panstw; ++i){
  72. cin >> Drzewo[i].nr_panstwa;
  73. cin >> Drzewo[i].wspolczynnik;
  74. }
  75. cin >> ilosc_zmian;
  76. int wczytywany_nr;
  77. int wczytywany_wspolczynnik;
  78. int ilosc_zmian_dok = 0;
  79. for(int j = 0; j < ilosc_zmian; ++j){
  80. cin >> wczytywany_nr;
  81. cin >> wczytywany_wspolczynnik;
  82. int pomocnicza = 0;
  83. int i = 0;
  84. while(1){
  85. if(wczytywany_nr != Drzewo[i].nr_panstwa){
  86. ++i;
  87. }
  88. else{
  89. pomocnicza = Drzewo[i].wspolczynnik;
  90. Drzewo[i].wspolczynnik = wczytywany_wspolczynnik;
  91. break;
  92. }
  93. }
  94. if(Drzewo[i].wspolczynnik > pomocnicza){
  95. ilosc_zmian_dok = przesiewaj_w_gore(Drzewo, i, ilosc_zmian_dok);
  96. }
  97. else if(Drzewo[i].wspolczynnik < pomocnicza){
  98. ilosc_zmian_dok = przesiewaj_w_dol(Drzewo, i, liczba_panstw, ilosc_zmian_dok);
  99. }
  100. i = 0;
  101. }
  102. //for(int k = 0; k < liczba_panstw; ++k){
  103. //cout << endl;
  104. //cout << Drzewo[k].nr_panstwa << ' ' << Drzewo[k].wspolczynnik;
  105. //cout << endl;
  106. //}
  107. cout << endl << ilosc_zmian_dok;
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement