maximus12793's blog

By maximus12793, history, 10 years ago, In English

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()
  • Vote: I like it
  • -13
  • Vote: I do not like it

| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Python's Queue class is designed for multithreading environments and hence is rather slow. You should use collections.deque instead. I made this change to your code and it got past test 18 but instead exceeds the memory limit on test 25. See 21592675.