ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1005. Stone Pile

Bit shifting takes too much time in python.
Posted by master8282 6 Feb 2018 23:02
import cProfile

length = int(input())
string = input()
row = list(map(int, string.split()))
halfrow = sum(row)/2
beg = eval('0b11'+ (length - 1) * '0')
end = eval('0b1'+ length * '1')

def func():

res = halfrow
for i in range(beg, end):
summa = 0

for j in range(length):

if i >> j & 1 == 1:
summa += row[j]

diff = abs(halfrow - summa)

if diff == 0:
return 0

if diff < res:
res = diff
return int(res * 2)

cProfile.run('print(func())')

\$ cat 1005
20
101 51 51 3 2 2 40 23 895 345 4 38 678 97 12 234 55 8054 26 108

\$ cat 1005 | python3 untitled19.py
5289
524292 function calls in 3.163 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    3.163    3.163 <string>:1(<module>)
1    3.107    3.107    3.163    3.163 untitled19.py:10(func)
524287    0.056    0.000    0.056    0.000 {built-in method builtins.abs}
1    0.000    0.000    3.163    3.163 {built-in method builtins.exec}
1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

So, why same method of solutions takes about 0.1 sec for C++ and about 3.1 sec for python?
The most loaded place is bit shifting.