paiza POH ec-Kampagne (Python / Ruby) (nicht gut abgestimmt)

Ich habe versucht, C ++ Nr. 3 nach Python und Ruby zu portieren (Unterscheidet sich die Situation von Python- und Ruby-Arrays von C (++)? Die Bucket-Sortierung hat sie langsamer gemacht).

Python (0.54s) Ich verschwende es, um auch mit 3.3 zu arbeiten http://paiza.jp/poh/ec-campaign/result/99a7b5e35cf1bd095e45504931c15635

paizapoh1.py

#!/usr/bin/python
import sys,bisect
if sys.version_info[0]>=3:
	raw_input=input
	xrange=range

n,d=[int(e,10) for e in raw_input().split()]
v=sorted([int(raw_input(),10) for i in xrange(n)])
for i in xrange(d):
	m=int(raw_input())
	r=j=0
	#k=n-1
	k=bisect.bisect_right(v,m-v[0])-1
	while j<k and v[j]+v[j+1]<=m:
		while v[j]+v[k]>m: k-=1
		if r<v[j]+v[k]:
			r=v[j]+v[k]
			if r==m: break
		j+=1
	print(r)

Ruby (0.34s) Da Paizas Rubin 1.9.3 ist, wird er aus dem Backport-Juwel zitiert. Wenn es 2.0.0 ist, ist der bsearch-Teil in der Sprache C, also schneller. http://paiza.jp/poh/ec-campaign/result/885ab06217b9e35f56b2baaf8193ba2d

paizapoh1.rb

#!/usr/bin/ruby
#https://github.com/marcandre/backports/blob/master/lib/backports/2.0.0/range/bsearch.rb
unless Range.method_defined? :bsearch
  class Range
    def bsearch
      return to_enum(:bsearch) unless block_given?
      from = self.begin
      to   = self.end
      unless from.is_a?(Numeric) && to.is_a?(Numeric)
        raise TypeError, "can't do binary search for #{from.class}"
      end

      midpoint = nil
      if from.is_a?(Integer) && to.is_a?(Integer)
        convert = Proc.new{ midpoint }
      else
        map = Proc.new do |pk, unpk, nb|
          result, = [nb.abs].pack(pk).unpack(unpk)
          nb < 0 ? -result : result
        end
        from = map['D', 'q', to.to_f]
        to   = map['D', 'q', to.to_f]
        convert = Proc.new{ map['q', 'D', midpoint] }
      end
      to -= 1 if exclude_end?
      satisfied = nil
      while from <= to do
        midpoint = (from + to).div(2)
        result = yield(cur = convert.call)
        case result
        when Numeric
          return cur if result == 0
          result = result < 0
        when true
          satisfied = cur
        when nil, false
          # nothing to do
        else
          raise TypeError, "wrong argument type #{result.class} (must be numeric, true, false or nil)"
        end

        if result
          to = midpoint - 1
        else
          from = midpoint + 1
        end
      end
      satisfied
    end
  end
end

n,d=gets.split.map(&:to_i)
v=n.times.map{gets.to_i}.sort
d.times{
	m=gets.to_i
	r=j=0
	k=((0...v.size).bsearch{|i|m-v[0]<v[i]}||v.size)-1 # upper_bound-1
	while j<k&&v[j]+v[j+1]<=m
		k-=1 while v[j]+v[k]>m
		if r<v[j]+v[k]
			r=v[j]+v[k]
			break if r==m
		end
		j+=1
	end
	p r
}