|
|
back to boardPython 2.7 MLE. Any idea why? def binary_search(seq, t): min = 0; max = len(seq) - 1 while 1: if max < min: return False m = (min + max) / 2 if seq[m] < t: min = m + 1 elif seq[m] > t: max = m - 1 else: return True
n = int(raw_input()) prof_dates = [] for x in range(n): inp = int(raw_input()) if binary_search(prof_dates,inp) == False: prof_dates+=[inp]
k = int(raw_input()) counter = 0 for x in range(k): inp = int(raw_input()) if binary_search(prof_dates,inp): counter+=1 print counter Re: Python 2.7 MLE. Any idea why? Use xrange instead of range. Edited by author 02.04.2013 17:20 Re: Python 2.7 MLE. Any idea why? using xrange will give TL on 8 I suspect that it is impossible to get it accepted using Python for this problem. because the raw_input(), input() is very slow. correct me if I am wrong. Re: Python 2.7 MLE. Any idea why? Re: Python 2.7 MLE. Any idea why? Re: Python 2.7 MLE. Any idea why? Ok, if a faster I/O is used (read all once), using stdin.read().split(), it will give ML on test 8. In fact, read all to memory will cost ML regardless whatever algorithm you use. #!/usr/bin/env python from sys import stdin lines = stdin.read().split() n = int(lines[0]) p = [0] * n for i in xrange(1, n + 1): p[i - 1] = int(lines[i]) def chk(s, p, n): left = 0 right = n - 1 while left <= right: mid = (left + right) / 2 if s > p[mid]: left = mid + 1 elif s < p[mid]: right = mid - 1 else: return True return False c = 0 m = int(lines[n + 1]) for i in xrange(m): s = int(lines[n + 2 + i]) if chk(s, p, n): c += 1 print(c) Re: Python 2.7 MLE. Any idea why? You tried to store 1.000.000 of string objects in memory. Let's see the sizes of such string and list in bytes: >>> import sys >>> sys.getsizeof('1000000000') 43 >>> sys.getsizeof('1 1'.split()) 160 Re: Python 2.7 MLE. Any idea why? Yes. Read all to memory is not feasible. but without this, how to achieve a faster I/O than raw_input, input()? Re: Python 2.7 MLE. Any idea why? |
|
|