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

Timeout in 546 D
Автор Kuber, история, 11 месяцев назад, По-английски

Hi everyone, Please review my submission: https://codeforces.com/problemset/submission/546/213448834

The logic is exactly the same as that of the person who got the first position in the contest. I'm unable to understand how to change the solution to get AC.

Edit: Changed cout to printf and cin to scanf.

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

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

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

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

here testcase == 1e6 and for each test case your solve function runs at least 5e6 time(considering only the outer for loop), so in total your time complexity will be at least 1e6 * 5e6 == 5e12 which gives TLE. U can not calculate the sieve array every time. Rather pre-calculate the sieve only once before taking any input.

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

    Read the code again. Notice that solve is called exactly once (and thus, sieve runs once). The test cases are solved inside solve in the last for-loop with $$$n$$$ being number of test cases.

    Also, OP already solved the problem by changing cin/cout to scanf/printf: 213448834

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

you can try adding ios_base::sync_with_stdio(0); cin.tie(0); right inside your main

example:

int main（）{

ios_base::sync_with_stdio(0); cin.tie(0);

int t; cin>>t;

while(t--) solve();

}

→ Ответить