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

Why TLE
Автор luka25, история, 7 лет назад, По-английски

I've written the solution for 543 B,I think it works fine but gets time limit on test 8.I ckecked and it doesn't pass inputing phase.How can it happen with 3000 numbers?

My submission

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

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

Auto comment: topic has been updated by luka25 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by luka25 (previous revision, new revision, compare).

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

Use faster I/O. You can either use ios_base::sync_with_stdio(0);cin.tie(0); at the beginning of your program and continue using cin/cout or use scanf/printf.

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

    will it help on 3000 numbers?

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

      If the problem with your code is not the algorithm, it should make a significant difference. Input with these techniques can be more than 5 times faster.

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

special for you fixed code .

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

i didn't consider map is logN just changing to unordered_map fixed it.

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

    Your code awesome beautiful!!! Are you understand why std::map — TLE, std::unordered_set — AC ??

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

      I used map instead of array because it can be cleared more easily, didn't think of it being too slow.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится 
        std::map<int> mp;
......
mp.clear(); // seems more easily, actually it very-very heave operation - it destroyed many of memory.


//--------------------------
bool visited[1<<17];

....
memset(visited, 0, sizeof(visited)); // actually very cheap operation than std::map<>::clear.
        → Ответить