python 2.7 too slow test 18

Правка en1, от maximus12793, 2016-10-19 08:45:29

http://codeforces.me/contest/515/problem/D http://codeforces.me/contest/515/submission/21582967 Im getting a tle on test 18. Is there anything I can do to improve this vs rewriting in c++? I added the ct/z flags to make sure I save 1 extra loop in the case that I filled all tiles or produced no degree 1 edges. I implemented the same strategy as in their editorial but somehow it is too slow. (http://codeforces.me/blog/entry/16468) ideas? ~~~~~ from Queue import Queue

def main(): q = Queue() n, m = map(int,raw_input().split()) grid = [list(raw_input()) for x in xrange(n)] z = True while z: ct=0 z = False for r in xrange(n): for c in xrange(m): if grid[r][c] == '*': ct+=1 if grid[r][c] == '.': deg = 0 up = left = right = down = False if c+1<m and grid[r][c+1] == '.': deg +=1 right = True if r+1<n and grid[r+1][c] == '.': deg +=1 down = True if r-1>=0 and grid[r-1][c] == '.': deg +=1 up = True if c-1>=0 and grid[r][c-1] == '.': deg +=1 left = True if deg == 1: z = True #if we hit a degree 1 we may have created another if left: q.put((r,c-1,'<')) q.put((r,c,'>')) grid[r][c-1] = '@' #mark this so we dont overwrite it #with another configuration and skip it in the main loop if up: q.put((r-1,c,'^')) q.put((r,c,'v')) grid[r-1][c] = '@' if down: q.put((r,c,'^')) q.put((r+1,c,'v')) grid[r+1][c] = '@' if right: q.put((r,c,'<')) q.put((r,c+1,'>')) grid[r][c+1] = '@'

if(q.qsize()+ct) >= n*m:
        z = True 
        break

if z == False:
    print "Not unique"
    return 
while q.empty() == False:
    x,y,s = q.get()
    if grid[x][y] == '.' or grid[x][y] == '@':
        grid[x][y] = s
    else:
        continue
for i in grid:
    print ''.join(i)

if name == '__main__': main()

~~~~~

Теги #timelimit, python 2, python faster thanc,c++, optimization, contest time

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский maximus12793 2016-10-19 08:45:57 4 Tiny change: ') ideas?\n~~~~~\nfrom Que' -
en1 Английский maximus12793 2016-10-19 08:45:29 2813 Initial revision (published)