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

e-olimp, 7325 задача, вердикт Memory limit
Автор Wild_Hamster, 10 лет назад, По-русски

Не могу понять, почему выбивает memory limit. Использование памяти в моем коде примерно O(2^(n/2)), при ограничениях 64МБ не должно бы вроде быть такого вердикта. Подскажите пожалуйста, что не так. Мой код. Задача.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

Мэпы же. Они не мало памяти кушают на саму структуру дерева.

А так как у вас ещё и WA на некоторых тестах проскакивает, то может и лишнего чего в них кладёте.

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

    А сколько именно памяти требует мэп?

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

      Если верить Запуску на КФе, то 24 дополнительных байта на каждый элемент у G++, и 32 байта у VC++.

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

        все равно никак не могу найти, где я что-то лишнее кладу. Максимум, что насчитал — (2^20)*32 < 64Мб

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

          По моим подсчётам у вас 50-60 МБ должно быть. С WA разберитесь сначала, а там может и ML исчезнет.

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

          Собственно возможная причина МЛ: когда вы обращаетесь к мэпу через оператор [], то элемент в контейнере создаётся, если его не было. 67-я строка вашего решения.

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

            а можно еще как-то обращаться, кроме как []?

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

              Проверка на наличие элемента в мапе:

              m.find(x) != m.end()

              Сделать что-то с элементом, если он есть:

              map<T>::iterator it = m.find(x);

if (it != m.end())
{
    it->second = new_value;
}
              → Ответить