Submission #14164516

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(N,K,D),A = 2.times.map{ gets.split.map(&:to_i) }
m = A.map.with_index{|a,i| [a,i,i,i+1,nil,nil] }
m = m.each_slice(2).map{|l,r|
  r = l unless r
  min = l[0]<r[0]||l[0]==r[0]&&l[1]<r[1] ? l : r
  next [min[0],min[1],l[2],r[3],l,r]
} until 1 == m.size
Min = lambda{|b,e|
  next nil unless b<e
  q,a,i = [m[0]],nil,nil
  until q.empty?
    a_,i_,b_,e_,l,r = q.shift
    if b<=b_ && e_<=e
      (a,i = a_,i_) if (! a || a_<a || a_==a && i_<i)
    else
      q << l if b<l[3]
      q << r if r[2]<e
    end
  end
  next a,i
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

(N,K,D),A = 2.times.map{ gets.split.map(&:to_i) }

m = A.map.with_index{|a,i| [a,i,i,i+1,nil,nil] }
m = m.each_slice(2).map{|l,r|
	r = l unless r
	min = l[0]<r[0]||l[0]==r[0]&&l[1]<r[1] ? l : r
	next [min[0],min[1],l[2],r[3],l,r]
} until 1 == m.size
Min = lambda{|b,e|
	next nil unless b<e
	q,a,i = [m[0]],nil,nil
	until q.empty?
		a_,i_,b_,e_,l,r = q.shift
		if b<=b_ && e_<=e
			(a,i = a_,i_) if (! a || a_<a || a_==a && i_<i)
		else
			q << l if b<l[3]
			q << r if r[2]<e
		end
	end
	next a,i
}

b,B = -D,[]
K.downto(1){|k|
	min,i = Min[b+D, N-D*(k-1)]
	break unless min
	B << min
	b = i
}
puts(B.size==K ? B.join(" ") : -1)

Submission Info

Judge Result