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

Автор HUECTRUM1, история, 8 лет назад, По-русски

Я попытался сдать задачу декартовыми деревьями, и получил TLE10. Также оно еле укладывается в TL по задаче D отсюда: http://codeforces.me/gym/100093 (а если все приоритеты брать по mod1000, то оно ловит TLE15) и проваливает F.

Допустил ли я где-то ошибку, или ни одна из этих задач не должна сдаваться декартовыми деревьями?

Посылки:

Задача D из тренировок

Задача F из тренировок

По неведомой причине залетевшее решение F

SPOJ

(В процессе написания у меня почему-то зашла F, но поскольку это случилось 1 раз из 4, этим, видимо, стоит пренебречь).

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

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

rand() вроде возвращает 15-битное число, попробуй (rand() << 15) | rand() вместо этого

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

    А ещё лучше — (rand() << 16) ^ rand() (основное — ^ вместо |), тогда будет генерировать случайные числа независимо от того, 16 бит выдаёт или больше.

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

      Тогда уже без UB ((unsigned)rand() << 16) ^ rand() и хранить в unsigned

      http://ideone.com/dPcCUi

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

        или таки начать использовать то, что заведомо нормально работает

        std::uniform_int_distribution<>([l,r если надо])(gen);
        
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

          Кто-нибудь, замутите пикчу наподобие этой вида:


          srand(42); | // чёткая int y = (rand() << 16) ^ rand(); | // аватарка | // yeputons ================================================================== | // размазанная std::random_device rd; | // аватарка std::mt19937 gen(rd()); | // AlexDmitriev типа std::uniform_int_distribution<> dis(0, 1 << 30); | // многобукоф ни int y = dis(gen); | // о чём
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            std::mt19937 gen(69);
            int y = gen();
            

            Для декартова дерева мне норм.

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

              Так да, норм.

              Я всего-лишь придрался к std::uniform_int_distribution<>, которым, кажется, можно подпирать потолок, если положить на бок.

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

            ну если честно сравнивать, то первая строчка не нужна и просидировать можно напрямую.

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

Задача F solution Проблема не только в рандом, лучше не используй std::cin, std::cout , even sync_with_stdio(false). Лучше используй printf/scanf Твое решение почти идентичен с моим, кроме метод чтение/запись.

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

    Кстате кто-нибудь знает решение Задача F с помощью дерево интервалов, буду блогадарень если опишите решение.