Submission #7605608

---

Source Code Expand

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)
function bsearch(a,x);l,r=0,length(a)+1;while r-l>1;m=(r+l)>>1;if a[m]<x;l=m;else;r=m;end;end;r;end

function sim(e::Array{Array{Array{Int,1},1},1},x::Int)
	now = x
	num = 0
	while 1==1
		k = bsearch(e[now][1],num+1)
		if k>length(e[now][1])
			break
		else
			num = e[now][1][k]
			now = e[now][2][k]
		end
	end
	now
end

function main()
	n,m,d = readline() |> split |> parseMap
	a = readline() |> split |> parseMap
	e = [[Int[],Int[]] for i in 1:n]
	for i in 1:m
		push!(e[a[i]][1], i)
		push!(e[a[i]][2], a[i]+1)
		push!(e[a[i]+1][1], i)
		push!(e[a[i]+1][2], a[i])
	end
	r = 0
	while 2^r<=d
		r += 1
	end
	dp = zeros(Int,r,n)
	for i in 1:n
		dp[1,i] = sim(e,i)
	end
	for i in 2:r
		for j in 1:n
			dp[i,j] = dp[i-1,dp[i-1,j]]
		end
	end
	s = parseMap(split(bin(d,2),""))
	l = length(s)
	for i in 1:n
		now = i
		for j in 0:l-1
			if s[l-j]==1
				now = dp[j+1,now]
			end
		end
		println(now)
	end
end

main()

Submission Info

Judge Result