Can anyone please explain why my second solution is getting tle ?
I just used push_front() instead of push_back() here.
First Solution — 188254737
Second Solution — 188254960
Problem — 1527E - Partition Game
Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 3803 |
2 | jiangly | 3707 |
3 | Benq | 3627 |
4 | ecnerwala | 3584 |
5 | orzdevinwang | 3573 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | Radewoosh | 3542 |
9 | jqdai0815 | 3532 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 163 |
2 | maomao90 | 160 |
3 | adamant | 159 |
4 | maroonrk | 152 |
5 | -is-this-fft- | 150 |
6 | atcoder_official | 148 |
6 | SecondThread | 148 |
8 | nor | 147 |
9 | TheScrasse | 146 |
10 | Petr | 144 |
Can anyone please explain why my second solution is getting tle ?
I just used push_front() instead of push_back() here.
First Solution — 188254737
Second Solution — 188254960
Problem — 1527E - Partition Game
Thanks in advance.
Name |
---|
I took a quick look at the source code for libstdc++, but I couldn't really figure out a concrete version one would be faster than the other. In the source code, deques start empty, so
push_front
allocates a block at the front andpush_back
allocates a block at the back. However, I think this should be basically the same speed.For testing on my own, I wrote the following program:
Running this with
push_back
five times, the times I get are: - 374ms - 358ms - 358ms - 358ms - 436msWith
push_front
, I get: - 514ms - 483ms - 436ms - 405ms - 529ms(I also modified some other comment to produce new runs for each program)
So it seems like with this program,
push_front
was worse.Running locally, I get:
and
So it looks like
push_back
is better locally as well, so maybe in general its better to usepush_back
, but I don't really know why this is true after looking at the source code.