When I was solving the problem 674G — Choosing Ads, I got a TLE on #10 as result. The submission id is 348821830.
I tried to generate a data and run my code on my Ubuntu, and it took 5.80 seconds. (The python code to generate the data is at the end of this blog.)
I was once told that O2 can make the code run faster, so I tried to compile the code with option -O2 (the full command was like g++ ./t.cpp -o ./t -O2), it just took 0.73s. I added #pragma GCC optimize(2) into the code, and then recompiled it without option -O2 (the full command was like g++ ./t.cpp -o ./t), however it took more than 5 seconds. (I used the command /usr/bin/time -v ./t < ./t.in > ./t.out to measure the time.)
As you can see the two ways above has a huge difference.
I'm wondering why this phenomenon happened.
Is there some problem in my code or the way I compile it? or it can just happen on my Ubuntu?
Thanks a lot.
#!/bin/python3
from random import *
n=150000
m=150000
k=20
print(n,m,k)
for _ in range(n):
print(randint(1,6),end=' ')
print()
for _ in range(m):
o=randint(1,2)
l=randint(1,n)
r=randint(1,n)
v=randint(1,6)
if l>r:
l,r=r,l
if o==1:
print(o,l,r,v)
else:
print(o,l,r)
When I was testing on my Ubuntu, all tests generated by this code will cause the phenomenon above.
Update
I've put #pragma GCC optimize(2) to the first line, then the time reduced to 3.13 seconds, still far more than -O2.
Update #2
I've passed it. I changed the map and vector to simple arrays like a[150005], which seems to be a good way to improve speed. On the local test, it took just about 0.5 second. But why there was such a huge difference on pragma and -O2?