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
Submission Time | |
---|---|
Task | E - Papple Sort |
User | kou65536 |
Language | Ruby (2.3.3) |
Score | 800 |
Code Size | 1689 Byte |
Status | AC |
Exec Time | 1273 ms |
Memory | 29736 KB |
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
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 1245 ms | 29464 KB |
02.txt | AC | 1271 ms | 29464 KB |
03.txt | AC | 1234 ms | 29464 KB |
04.txt | AC | 1267 ms | 29464 KB |
05.txt | AC | 1241 ms | 29464 KB |
06.txt | AC | 1273 ms | 29464 KB |
07.txt | AC | 1273 ms | 28824 KB |
08.txt | AC | 1230 ms | 29464 KB |
09.txt | AC | 1265 ms | 29464 KB |
10.txt | AC | 1231 ms | 29464 KB |
11.txt | AC | 109 ms | 6908 KB |
12.txt | AC | 109 ms | 6780 KB |
13.txt | AC | 109 ms | 6908 KB |
14.txt | AC | 109 ms | 6908 KB |
15.txt | AC | 1196 ms | 27936 KB |
16.txt | AC | 1209 ms | 27932 KB |
17.txt | AC | 1203 ms | 27776 KB |
18.txt | AC | 1200 ms | 29736 KB |
19.txt | AC | 1209 ms | 27704 KB |
20.txt | AC | 106 ms | 6004 KB |
21.txt | AC | 1238 ms | 27664 KB |
22.txt | AC | 1220 ms | 27664 KB |
23.txt | AC | 1233 ms | 27516 KB |
24.txt | AC | 104 ms | 6012 KB |
25.txt | AC | 1206 ms | 27904 KB |
26.txt | AC | 1210 ms | 27904 KB |
27.txt | AC | 1205 ms | 27416 KB |
28.txt | AC | 1186 ms | 27888 KB |
29.txt | AC | 1231 ms | 27484 KB |
30.txt | AC | 106 ms | 6112 KB |
31.txt | AC | 1201 ms | 27492 KB |
32.txt | AC | 104 ms | 6012 KB |
33.txt | AC | 1195 ms | 27560 KB |
34.txt | AC | 104 ms | 6008 KB |
35.txt | AC | 1209 ms | 27764 KB |
36.txt | AC | 104 ms | 6008 KB |
37.txt | AC | 106 ms | 5936 KB |
38.txt | AC | 108 ms | 6004 KB |
39.txt | AC | 1252 ms | 27608 KB |
40.txt | AC | 107 ms | 6004 KB |
41.txt | AC | 11 ms | 2044 KB |
42.txt | AC | 11 ms | 2044 KB |
43.txt | AC | 11 ms | 2044 KB |
44.txt | AC | 11 ms | 2044 KB |
45.txt | AC | 11 ms | 2044 KB |
46.txt | AC | 11 ms | 2044 KB |
47.txt | AC | 11 ms | 2044 KB |
s1.txt | AC | 11 ms | 2044 KB |
s2.txt | AC | 11 ms | 2044 KB |
s3.txt | AC | 11 ms | 2044 KB |