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 | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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.