fork(1) download
  1. #include <iostream>
  2. #include <cstdlib> //calloc()
  3. #include <utility> //pair
  4. #include <algorithm> //min(), max()
  5. using namespace std;
  6.  
  7. const int capacity = 100; //ёмкость каждого узла списка
  8.  
  9. template <class T> //T - тип данных, хранящихся в стеке
  10. class stack{
  11. private:
  12. struct node{ //основа стека неограниченной вместительности - односвязный список массивов
  13. node* prev; //указатель на предыдущий узел
  14. T* storage; //массив данных, хранящихся в текущем узле
  15.  
  16. node(){ //конструктор по умолчанию
  17. prev = nullptr; //список содержит всего один узел
  18. storage = (T*)calloc(capacity+1, sizeof(T)); //выделить память под capacity элементов заданного типа
  19. }
  20. node(node* predecessor){ //параметрический конструктор: добавление нового узла в список
  21. prev = predecessor; //последний узел старого списка будет предшественником нового узла
  22. storage = (T*)calloc(capacity+1, sizeof(T)); //в отличие от malloc, calloc заполняет выделенный участок памяти нулями
  23. }
  24. ~node(){ //деструктор
  25. free(storage); //очистить участок памяти, в котором хранится текущий узел
  26. }
  27. };
  28. node* container; //односвязный список
  29. int pos; //текущая позиция указателя. Используется 1-индексация массивов.
  30. int stored; //количество хранимых в данный момент элементов
  31.  
  32. public:
  33. stack(){ //конструктор по умолчанию
  34. container = new node(); //создать список из одного узла
  35. pos = stored = 0; //0 - служебная позиция, сигнализирующая о том, что стек пуст
  36. }
  37. //(в решении задачи не используется, но объявлять конструктор без деструктора - дурной тон - прим.)
  38. ~stack(){ //деструктор
  39. while(container != nullptr){ //пока список не пуст
  40. node* predecessor = container->prev; //сохранить указатель на предшествующий узел
  41. delete container; //очистить текущий узел
  42. container = predecessor; //перейти к предшествующему узлу
  43. }
  44. pos = stored = 0; //сбросить счетчик и указатель на позицию в стеке
  45. }
  46.  
  47. bool empty(){ //проверка на пустоту
  48. return stored == 0;
  49. }
  50.  
  51. int size(){ //количество элементов в стеке
  52. return stored;
  53. }
  54.  
  55. T top(){ //крайний элемент стека
  56. return container->storage[pos];
  57. }
  58.  
  59. void push(T x){ //добавление элемента
  60. if(pos == capacity){ //если текущий узел заполнен
  61. container = new node(container); //создать новый узел
  62. pos = 0; //и явно указать, что он пуст
  63. }
  64. container->storage[++pos] = x; //добавить элемент в стек
  65. ++stored; //количество хранимых элементов увеличилось на 1
  66. }
  67.  
  68. void pop(){ //удаление элемента
  69. if(pos == 1 && stored >= capacity){ //извлекается последний элемент крайнего узла списка
  70. node* predecessor = container->prev; //сохранить указатель на предыдущий узел
  71. delete container; //очистить память, занимаемую пустым узлом
  72. container = predecessor; //обновить указатель на текущий узел
  73. pos = capacity + 1; //удаление элемента эквивалентно сдвигу указателя влево
  74. //во избежание дублирования участка кода, указателю было присвоено значение
  75. //сдвигом влево которого будет получен указатель на крайний элемент узла
  76. }
  77. --stored; //число хранимых элементов уменьшается на единицу
  78. --pos; //указатель на текущую позицию сдвигается на единицу влево
  79. }
  80.  
  81. void clear(){ //очистка содержимого стека
  82. while(container != nullptr){ //если список не пуст
  83. node* predecessor = container->prev; //сохранить указатель на предшествующий узел
  84. delete container; //очистить текущий узел
  85. container = predecessor; //перейти к предшествующему узлу
  86. }
  87. container = new node(); //в отличие от деструктора, в списке оставляется один узел
  88. pos = stored = 0; //сброс значений счетчика и указателя на текущую позицию
  89. }
  90.  
  91. };
  92.  
  93. //модифицированные стеки: первый элемент пары - хранимое значение, второй - минимум в данной позиции
  94. stack<pair<long long, long long>> head, tail; //голова и хвост очереди
  95. //head - стек, из которого только удаляют элементы
  96. //tail - стек, в который только добавляют элементы
  97.  
  98. int main(){
  99. int n; cin >> n; //количество операций с очередью
  100. long long a, b, c, x, min_sum = 0;
  101. cin >> a >> b >> c >> x;
  102. while(n--){
  103. x = (a*x*x + b*x + c)/100 % 1000000;
  104. if(x % 5 < 2){ //удалить элемент из очереди
  105. if(head.empty()){ //если соответствующий стек пуст
  106. while(!tail.empty()){ //то перебросить в него содержимое другого стека
  107. long long value = tail.top().first;
  108. tail.pop();
  109. long long minimum = head.empty() ? value : min(head.top().second, value);
  110. head.push({value, minimum});
  111. }
  112. //по окончании обмена принцип FIFO не нарушен, так как элементы
  113. //хвоста очереди расположены в голове в порядке, обратном исходному
  114. }
  115. if(!head.empty()) //если очередь непуста
  116. head.pop(); //удалить первый элемент очереди
  117. }
  118. else{ //добавить элемент в очередь
  119. if(tail.empty()) //если соответствующий стек пуст
  120. tail.push({x, x}); //то добавленный элемент также является текущим минимумом
  121. else //в противном случае
  122. tail.push({x, min(x, tail.top().second)}); //если добавленный элемент меньше всех, содержащихся в стеке
  123. //то обновить текущий минимум
  124. }
  125. if(tail.empty() ^ head.empty()) //если не пуст или первый, или второй стек (но не оба одновременно)
  126. min_sum += tail.empty() ? head.top().second : tail.top().second; //прибавить к сумме доступный минимум
  127. else //если оба стека одновременно либо пусты, либо нет
  128. min_sum += tail.empty() ? 0 : min(tail.top().second, head.top().second); //либо не изменить сумму, либо добавить к ней минимум
  129. //из значений, хранящихся в обоих стеках
  130. }
  131. cout << min_sum << endl; //минимально возможная после всех манипуляций сумма
  132. }
  133.  
Time limit exceeded #stdin #stdout 5s 3232KB
stdin
Standard input is empty
stdout
Standard output is empty