Блог пользователя computerbox

Автор computerbox, 5 лет назад, По-русски

Всем привет ! Я решаю задачу Следующий на e-olymp ( https://www.e-olymp.com/ru/problems/686) и у меня в вердикте выдает превышено ограчение памяти . Как это исправить я не знаю. Помогите мне исправить это .

Код
  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Do not use "new" operation. You can prepare a pool for the allocation of space.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    I don't know ,how i can do this. Can you show ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Also, consider using 32-bit integer handles instead of pointers. On 64-bit systems, this will cut your memory usage in half.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      1.Create a container of max required size

      2.Use a stack to keep track of available indexes.

      // define the max required space
      #define MAX_SIZE 600005
      
      //create a container of max size
      int array[MAX_SIZE];
      stack available;
      
      //store all available index in stack
      void init()
      {
          for (int i=0; i<MAX_SIZE; i++)
          available.push(i);
      }
      
      //get will give index of any available space and remove it from available
      int get()
      {
          int index=available.top();
          available.pop();
          return index;
      }
      
      //in order to delete, add it back to stack
      void free(int index)
      {
          available.push(index);
      }
      

      This technique provides better speed while execution since dynamic allocation of memory is not done. The problem is the max required space must be known in advance.

      P.S. The answer is written using a phone, so there might be issues with indentation and others.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thanks forgotter, i will try to understand it. Do you see my insert function ? I think all problems in this function. I think ,i implemented it very bad.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

rand() не очень хорошо подходит для инициализации приоритетов декартова дерева, так как на многих системах возвращает 16-битное число (ну и по некоторым другим причинам). Лучше использовать mt19937. Но это скорее не к памяти относится, а ко времени работы.

Также, видимо, замена long long на int в ключах и приоритетах уменьшит расходы памяти раза в полтора.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо большое за совет! Я попробую .

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BledDest вы были правы замена на int оптимизировала память ,но она к сожалению все ещё большая.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BledDest Мне почему-то кажется ,что я функцию insert плохо реализовал . Ведь память увеличивается ,когда мы добавляем вершину . Как я могу лучше написать ,используя меньше памяти ?