Kuber's blog

Timeout in 546 D
By Kuber, history, 10 months ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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();

}

→ Reply