fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A6BpwN
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!