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

Яндекс Квал 2, Задача С, TL 101
Автор Shtrix, 15 лет назад, По-русски
Замечательные впечатления оставил следующий эксперемент. Одно и тоже решение задачи С использующее priority_queue было сдано на двух компиляторах. 

Итог:

Visual Studio 2005: TL 101 (как и на контесте)
GCC 4.6+: AC, 1090ms

Посылки:
442400
442399

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

15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -7 Проголосовать: не нравится

Под студией свободно проходило с использованием не priority_queue, а своей рукописной кучи (330 мс), причем без всяких прочих модернизаций. Вывод: меньше priority_queue - больше профита ) и лениться не надо писать свой код, когда знаешь, что stl работает дольше
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +25 Проголосовать: не нравится
    Точно! Вы на всех контестах вместо мапа пишете свое сбалансированное двоичное дерево, или только на КФ?
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +8 Проголосовать: не нравится
      Я только про stl-кую очередь с приоритетами писал, вообще-то
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        у меня решение на priority_queue работает 530 мс, так-что не много вы выиграли написав ручками. А тайм лимит и правда плохой выставлен, совсем не очевидно что на сетах завалится, я просто подумал что мало-ли, и написал на очереди, а на сетах потом затлилось. оба решения писал в дорешке.
        → Ответить
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится

      Стандартные доводы: а вы умеете писать замену map так, чтобы она заработала без особого дебага?
      Я лично знаю несколько человек, которые пишут на C++, используя sort и ту же очередь с приоритетами, совершенно не имея представления, как это работает. Имхо, это плохо, т.к. такие простые вещи, раз уж ты их используешь, ты должен уметь реализовывать сам
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Я иронизировал конкретно по поводу фразы "и лениться не надо писать свой код, когда знаешь, что stl работает дольше". Ясно же, что ручной мап работает быстрее СТЛевского, но его никто не пишет.
        → Ответить
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Согласен насчет мапа, но тут конкретно про priority_queue разговор был. Мне кажется, в таких задачах, где правильное решение может не пройти по TL, имеет смысл оптимизировать,  в том числе заменяя шаблонные алгоритмы рукописными. Вон, люди пострадали
          → Ответить
          • 15 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится
            Конкретно в этой задаче надо было не приорити кью тогда уже оптимизировать, а асимптотику решения. А вообще, очень редко бывает что стлевской приорити кью не хватает, если авторами предполагалось именно это решение, а не более быстрое асимптотически.
            → Ответить
          • 15 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится
            c priority_queue зашло на 101 тесте за 550 млс, 102 - 580... Проблема видимо в неоптимальности других частей решения
            → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Попробуйте использовать make_heap.
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Разные оптимизаторы оптимизируют по разному. Это стандартное явление, более того, 2008 версия может работать намного быстрее 2005...а может и дольше...=)

По статистике вижак 2005 намного медленнее последнего GCC.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Если заменить

vector<bool> used;

на

vector<int> used;
то проходит на MS C++

→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
Может быть немножко оффтоп, но я написал решение с очередью на яве, в конце контеста посмотрел на время, понял что ни к чему хорошему эти 11 секунд не приведут. Переписал очень просто. без всяких структур, за N^2.
→ Ответить