Submission #2703296

---

Source Code Expand

require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

class BIT
	def initialize(n)
		# holding cells of 1..n
		@cells = Array.new(n+1){0}
		@i_max = n
	end
	def add(i,n)
		if(i <= 0)
			return
		end
		while(i<=@i_max)
			@cells[i] += n
			i += i & -i
		end
	end
	def sum(i)
		if(i > @i_max)
			return
		end
		sum = 0
		while(i>0)
			sum += @cells[i]
			i -= i & -i
		end
		return sum
	end
	# arr : n size array holding values from 1 to n
	def inversion_num(arr)
		sum = 0
		arr.each_with_index{|n,j|
			sum += j-self.sum(arr[j])
			self.add(arr[j],1)
		}
		return sum
	end
end

S=gets.chomp
size = S.size
h = {}
arr = Array.new(S.size)
0.upto(S.size-1){|i|
	h[S[i]].nil? ? h[S[i]]=[i] : h[S[i]] << i
}

dpp h

odds = h.select{|k,v| v.size % 2 != 0}
dpp odds
if(size%2==0 && odds.size > 0 || size%2!=0 && odds.size != 1)
	puts -1
	exit(0)
end
oddkey = odds.keys

rearr = []
ih = {}
h.each{|k,v| if(v.size > 1) then v[0..((v.size)/2-1)].each{|v| rearr << [k,v]} end}

dpp "rearr #{rearr}"

rearrmap = Array.new(size)
rearr = rearr.sort{|kv1,kv2| kv1[1] <=> kv2[1]}

dpp "sorted rearr #{rearr}"

rearr.each_with_index{|kv,i|
	k = kv[0]
	v = kv[1]
	ih[k].nil? ? ih[k]=0 : ih[k]+=1
	dputs "kv and i is #{kv} #{i}"
	dputs "ih[k] #{ih[k]} ih[k][-v-1] #{ih[k][-v-1]}"
	rearrmap[v] = i+1
	rearrmap[h[k][-ih[k]-1]] = size-i
}
if(!oddkey.empty?)
	oddkey = oddkey[0]
	tmp = odds[oddkey]
	tmpsize = tmp.size
	rearrmap[tmp[tmpsize/2]]=size/2+1
end

dpp rearrmap

bit = BIT.new(size)
puts bit.inversion_num(rearrmap)

Submission Info

Compile Error

./Main.rb:65: warning: ambiguous first argument; put parentheses or a space even after `-' operator
./Main.rb:72: warning: shadowing outer local variable - v
./Main.rb:55: warning: assigned but unused variable - arr

Judge Result