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

Comparing the given problem and time complexity of my solution, why is the time taken so high
Автор zzzzsust19, история, 20 месяцев назад, По-английски

Problem link: https://codeforces.com/problemset/problem/1294/D

My submission: https://codeforces.com/contest/1294/submission/172332862

The problem I am trying to solve has constraints as given, 1 <= q, x <= 4 * 10^5 The time complexity of the solution I have submitted is around O(2 * q). It's basically a linear time solution.

My expectation was that the highest time it would take would be around 100-200 ms. But the solution took around 1200 ms at worst case. Which is far higher than I expected. What is the reason behind this high time complexity

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

»
20 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Try this code:

int n = 200000;
for (int i = 0; i < n; i++) {
    cin >> a[i];
    cout << a[i] << '\n';
}

This code will be not fast. Because every time between std::cin and std::cout there runs a buffer flush operation.

To answer your question faster, use cin.tie(0) right after ios_base::sync_with_stdio

https://codeforces.com/contest/1294/submission/172333686 (without cin.tie)

https://codeforces.com/contest/1294/submission/172333645 (with cin.tie)

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

    Thank you very much for the info, I have faced many cases like this where I get higher execution time than expected, I believe this explains it.

    → Ответить