Advertisement
Guest User

Flappy Bird

a guest
Jan 16th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.45 KB | None | 0 0
  1. #include <cstdio>
  2. #include <stack>
  3.  
  4. using namespace std;
  5.  
  6. stack<int> otwarte;
  7.  
  8. int przeszkody[500001][3]; // 0-dol 1-gora 2-x
  9. int poz[500001][3]; // 0-roznica y-ów z poprz przeszkoda 1-y 2-liczba przeskokow
  10.  
  11. int mini(int a, int b)
  12. {
  13.     return a < b ? a : b;
  14. }
  15.  
  16. int main()
  17. {
  18.     //printf("%d\n", mini(5, 3));
  19.     int i, n, x, a, miny = 2e9, limit, wynik = 0, k, pom;
  20.     //printf("%d\n", (-4)%2);
  21.     scanf("%d %d", &n, &x);
  22.     for (i = 1; i <= n; i++)
  23.     {
  24.         scanf("%d %d %d", &a, &przeszkody[i][0], &przeszkody[i][1]);
  25.         przeszkody[i][0]++;
  26.         przeszkody[i][1]--;
  27.         if (a % 2 == 0)
  28.         {
  29.             if (przeszkody[i][0] % 2 != 0)
  30.                 przeszkody[i][0]++;
  31.             if (przeszkody[i][1] % 2 != 0)
  32.                 przeszkody[i][1]--;
  33.         }
  34.         else
  35.         {
  36.             if (przeszkody[i][0] % 2 == 0)
  37.                 przeszkody[i][0]++;
  38.             if (przeszkody[i][1] % 2 == 0)
  39.                 przeszkody[i][1]--;
  40.         }
  41.         przeszkody[i][2] = a;
  42.     }
  43.     for (i = 1; i <= n; i++)
  44.     {
  45.         if (przeszkody[i][0] > przeszkody[i][1])
  46.         {
  47.             //przeszkoda to tylko jeden nieosiagalny punkt
  48.             printf("NIE\n");
  49.             wynik = -1;
  50.             break;
  51.         }
  52.         if (poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]) > przeszkody[i][1])
  53.         {
  54.             //nie mozemy spasc
  55.             printf("NIE\n");
  56.             wynik = -1;
  57.             break;
  58.         }
  59.         else if (poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]) >= przeszkody[i][0])
  60.         {
  61.             //pelny spadek swobodny
  62.             przeszkody[i][0] = poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]);
  63.             poz[i][1] = przeszkody[i][0];
  64.             otwarte.push(i);
  65.             poz[i][0] = poz[i][1]-poz[i-1][1];
  66.             poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
  67.         }
  68.         else
  69.         {
  70.             if (przeszkody[i][0]-poz[i-1][1] > przeszkody[i][2]-przeszkody[i-1][2])
  71.             {
  72.                 //trzeba robic przeskok
  73.                 k = ((przeszkody[i][0]-poz[i-1][1])-(przeszkody[i][2]-przeszkody[i-1][2]))/2; //-l. przeskokow
  74.                 while(!otwarte.empty() && k > 0)
  75.                 {
  76.                     pom = otwarte.top();
  77.                     limit = mini(poz[pom][2], (poz[pom-1][1]+(przeszkody[pom][2]-przeszkody[pom-1][2])-poz[pom][1])/2);
  78.                     //TUTAJ NAPISZ PODNOSZENIE WYKRESU
  79.                     if (k <= limit)
  80.                     {
  81.                         wynik += k;
  82.                         poz[pom][1] += 2*k;
  83.                         poz[pom][0] += 2*k;
  84.                         poz[pom][2] -= k;
  85.                         if (poz[pom][0] == przeszkody[pom][2]-przeszkody[pom-1][2])
  86.                         {
  87.                             //ZAMYKAMY KRAWEDZ
  88.                             otwarte.pop();
  89.                             if (!otwarte.empty())
  90.                             {
  91.                                 poz[otwarte.top()][2] = mini(poz[otwarte.top()][2], poz[pom][2]);
  92.                             }
  93.                         }
  94.                         k = 0;
  95.                     }
  96.                     else
  97.                     {
  98.                         if (limit == 0)
  99.                             break;
  100.                         wynik += limit;
  101.                         k -= limit;
  102.                         poz[pom][1] += 2*limit;
  103.                         poz[pom][0] += 2*limit;
  104.                         poz[pom][2] -= limit;
  105.                         if (poz[pom][0] == przeszkody[pom][2]-przeszkody[pom-1][2])
  106.                         {
  107.                             //ZAMYKAMY KRAWEDZ
  108.                             otwarte.pop();
  109.                             if (!otwarte.empty())
  110.                             {
  111.                                 poz[otwarte.top()][2] = mini(poz[otwarte.top()][2], poz[pom][2]);
  112.                             }
  113.                         }
  114.                     }
  115.                 }
  116.                 if (k > 0)
  117.                 {
  118.                     printf("NIE\n");
  119.                     wynik = -1;
  120.                     break;
  121.                 }
  122.                 else
  123.                 {
  124.                     wynik += przeszkody[i][2]-przeszkody[i-1][2];
  125.                     poz[i][0] = przeszkody[i][2]-przeszkody[i-1][2];
  126.                     poz[i][1] = przeszkody[i][0];
  127.                     poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
  128.                     if (!otwarte.empty())
  129.                     {
  130.                         pom = otwarte.top();
  131.                         poz[pom][2] = mini(poz[pom][2], poz[i][2]);
  132.                     }
  133.                 }
  134.             }
  135.             else
  136.             {
  137.                 //nie trzeba
  138.                 wynik += (przeszkody[i][0]-(poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2])))/2;
  139.                 poz[i][1] = przeszkody[i][0];
  140.                 poz[i][0] = poz[i][1]-poz[i-1][1];
  141.                 poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
  142.                 if (poz[i][0] != przeszkody[i][2]-przeszkody[i-1][2])
  143.                 {
  144.                     otwarte.push(i);
  145.                 }
  146.                 else
  147.                 {
  148.                     if (!otwarte.empty())
  149.                     {
  150.                         pom = otwarte.top();
  151.                         poz[pom][2] = mini(poz[pom][2], poz[i][2]);
  152.                     }
  153.                 }
  154.             }
  155.         }
  156.     }
  157.     if (wynik != -1)
  158.         printf("%d\n", wynik);
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement