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

Проблема на SPOJ [done]
Автор Kostroma, 13 лет назад, По-русски
Сдаю сюда: http://www.spoj.pl/problems/SUBST1/ следующий код: http://pastebin.com/A9uhveJY
получаю ТЛ - видимо на 0 тесте (пишет running(0), а потом TLE)
из-за отсутствия каких-либо указаний по вводу-выводу понял, что он стандартный
дома 0-й тест, естественно, летает
не подскажете, в чем проблема? :)

P.S. не первая уже проблема с этим сайтом :(

UPD новый код: http://pastebin.com/tay46HG5

есть ли на другом сайте аналогичная задача? :)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Дак там мультитест. Неотптимальное решение скорее всего.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    вроде должно проходить по ассимптотике O(t * n * logn)
    правильно ли я понимаю, что 0-й тест должен совпадать с тестом из условия?
    ведь даже если дело в константе, то уж его-то должен проходить почти любой алгоритм :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Нет программа проверяется на одном большом тесте, и сложность, если я правильно понял O(t*n*logn*logn)
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        да, вы правы насчет сложности
        а, раз 1 большой тест, тогда понятно
        спасибо! :)
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
В дополнение посоветую использовать scanf/printf вместо cin/cout
Учитывая, что таймлимиты там выставлены достаточно жестко, такая оптимизация лишней не будет
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо, исправил. вообще привык когда  <  = 105 чисел использовать cin/cout
    тоже ТЛ, что собственно и ожидалось - вывод 21 числа особо ни на что не повлияет ))
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
получается в худшем случае около 256*10^6 операций * C 2 секунды ТЛ....
вообще можно решение с такой ассимпотикой пропихнуть?))
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
о ужас
зачем ставить ограничения, в которые нужно запихивать задачу всеми конечностями? О_о
или это чтобы только дерево проходило?
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
ACC  с помощью алгоритма Каваи!! :) Спасибо за помощь! :)
→ Ответить