I was doing this problem https://codeforces.me/contest/1822/problem/G1 recently, and I was comparing my code to the editorial implementation and I kept getting TLE again and again, trying to make the code more and more similar to the implementation given. The ultimate thing that allowed AC was changing the static array "a" to a vector of size n as in the implementation. Anyone know why the vector performs better? Because I thought static arrays were faster if anything.
My AC submission: https://codeforces.me/contest/1822/submission/280480288
My submission just before that (using static array a): https://codeforces.me/contest/1822/submission/280480106
(Just scroll down to the main function at the very bottom -- there is a bunch of template stuff above it not for the problem).
Thank you in advance for any help.
Auto comment: topic has been updated by ycperson (previous revision, new revision, compare).
This has nothing to do with vector or static array. https://codeforces.me/contest/1822/submission/280482428
Your static array has size $$$2 \cdot 10^5$$$, and we have $$$t \le 10^4$$$. Replaced this with
and got AC.
P.S. Also for some reason you have chosen old 32-bit C++-17 compiler instead of new 64-bit C++-20 compiler.
Ah yes. My neglect of the fact that n's sum over the tests has a bound, so there's a difference between what I did to restore array a, as opposed to the given implementation. Thank you.
the problem was not from the type of the array a .the problem was from it's size .
in your code you have this line
in the TLE code a.size()== $$$20^5+1$$$ and in the worst case scenario t= $$$10^4$$$ so it makes $$$20^9+1 $$$ iterations which is definitely a TLE
but the other code works because "The sum of n over all test cases does not exceed $$$20^5$$$ ."
Yes, that makes sense. Thank you as well.