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()

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

By maximus12793, history, 10 years ago, In English

http://codeforces.me/contest/378/submission/21474186

I have submitted the analogous code in c++ and it worked fine. Is there some reason why this does not work even having set the recursion limit to 20k? I have every time the time and memory is well within limit when it crashes. any ideas?

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

By maximus12793, history, 10 years ago, In English

verified here https://www.jdoodle.com/execute-go-online

and with 1.6 and 1.7 I have 0 issues with this code but as soon as i hit test 7 in http://codeforces.me/problemset/problem/448/D it breaks despite it working on every other site I try. any idea what the issue is?

package main

import "fmt"
import "math"

func calc(n int, m int, num int) int {
	maxi := int(math.Sqrt(float64(num)))
	re := 0
	for i := 1; i <= maxi; i++ {
		if num%i == 0 {
			se := num / i
			if (i <= n) && (se <= m) {
				re++
			}
			if (i <= m) && (se <= n) {
				re++
			}
			if (se == i) && (se <= n) && (se <= m) {
				re--
			}
		}
	}
	return re

}

func main() {
	var n, m, k int
	fmt.Scanf("%d %d %d\n", &n, &m, &k)
	var ans int64 = 9223372036854775807

	mini := 0
	maxi := n*m + 2
	for mini < maxi {
		var temp int = 0
		var mid int = int(mini+maxi) / 2
		var re int = calc(n, m, mid)
		for i := 1; i <= n; i++ {
			temp += int(math.Min(float64(mid/i), float64(m)))
		}
		var r1 int = temp - re + 1
		var r2 int = temp
		if (k <= r2) && (k >= r1) {
			mini++
			ans = int64(math.Min(float64(ans), float64(mid)))

		}
		if temp >= k {
			maxi = mid
		} else {
			mini = mid + 1
		}
	}
	fmt.Println(ans)
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it