Submission #2756669


Source Code Expand

Copy
lines = $stdin.read
array = lines.split("\n")

def msb(x)
  x.to_s(2).size - 1
end

def lsb(x)
  msb(x & -x)
end

N,M,Q = array[0].split(" ").map(&:to_i)
A     = if M == 0
          []
        else
          array[1].split(" ").map(&:to_i)
        end
to    = 1.upto(N).to_a

for a in A.reverse
  to[a], to[a-1] = to[a-1],to[a]
end

# doubling
LOGN = msb(Q)+1
next_obj = Array.new(LOGN+1).map{Array.new(N, 0)}

for i in 0...N
  next_obj[0][i] = to[i] - 1
end

for k in 0...LOGN
  for i in 0...N
    if next_obj[k][i] == -1
      next_obj[k+1][i] = -1
    else
      next_obj[k+1][i] = next_obj[k][next_obj[k][i]]
    end
  end
end

QBIT = Q.to_s(2).reverse

for p in 0...N
  pidx = p
  (1..LOGN).to_a.reverse_each do |k|
    if 1 == QBIT[k-1].to_i
      pidx = next_obj[k-1][pidx]
    end
  end
  puts pidx+1
end

Submission Info

Submission Time
Task D - 阿弥陀
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 863 Byte
Status
Exec Time 2013 ms
Memory 46972 KB

Compile Error

./Main.rb:46: warning: shadowing outer local variable - k

Test Cases

Set Name Score / Max Score Test Cases
Subtask1 10 / 10 sample_1.txt, 01_i.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt
Subtask2 20 / 20 sample_1.txt, sample_2.txt, sample_3.txt, 02_i.txt, 02_p.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_rp01.txt, 02_rp02.txt, 02_rp03.txt, 02_rp04.txt, 02_rp05.txt
Subtask3 20 / 20 sample_1.txt, sample_2.txt, 03_i.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt
Subtask4 50 / 50 sample_1.txt, sample_2.txt, sample_3.txt, 04_i.txt, 04_p1.txt, 04_p2.txt, 04_random01.txt, 04_random02.txt, 04_random03.txt, 04_random04.txt, 04_random05.txt, 04_random06.txt, 04_random07.txt, 04_random08.txt, 04_random09.txt, 04_random10.txt, 04_random11.txt, 04_random12.txt, 04_random13.txt, 04_rp01.txt, 04_rp02.txt, 04_rp03.txt, 04_rp04.txt, 04_rp05.txt, 04_rp06.txt, 04_rp07.txt, 04_rp08.txt, 04_rp09.txt, 04_rp10.txt
Case Name Status Exec Time Memory
01_i.txt 358 ms 24316 KB
01_random01.txt 7 ms 1788 KB
01_random02.txt 7 ms 1788 KB
01_random03.txt 7 ms 1788 KB
01_random04.txt 20 ms 2556 KB
01_random05.txt 257 ms 7312 KB
01_random06.txt 337 ms 21240 KB
01_random07.txt 364 ms 24316 KB
02_i.txt 17 ms 1916 KB
02_p.txt 16 ms 1916 KB
02_random01.txt 7 ms 1788 KB
02_random02.txt 7 ms 1788 KB
02_random03.txt 15 ms 2300 KB
02_random04.txt 16 ms 1916 KB
02_random05.txt 26 ms 4348 KB
02_random06.txt 67 ms 11644 KB
02_random07.txt 132 ms 21244 KB
02_random08.txt 133 ms 21244 KB
02_rp01.txt 16 ms 1916 KB
02_rp02.txt 16 ms 1916 KB
02_rp03.txt 14 ms 1916 KB
02_rp04.txt 16 ms 1916 KB
02_rp05.txt 16 ms 1916 KB
03_i.txt 7 ms 1788 KB
03_random01.txt 17 ms 3196 KB
03_random02.txt 115 ms 20092 KB
03_random03.txt 96 ms 18044 KB
03_random04.txt 95 ms 17916 KB
03_random05.txt 25 ms 4476 KB
03_random06.txt 23 ms 4348 KB
03_random07.txt 33 ms 4860 KB
03_random08.txt 9 ms 1916 KB
03_random09.txt 41 ms 7164 KB
03_random10.txt 67 ms 11388 KB
03_random11.txt 114 ms 19836 KB
03_random12.txt 115 ms 19964 KB
03_random13.txt 91 ms 16892 KB
03_random14.txt 73 ms 11772 KB
03_random15.txt 32 ms 4860 KB
04_i.txt 2013 ms 46972 KB
04_p1.txt 1889 ms 36220 KB
04_p2.txt 1471 ms 29304 KB
04_random01.txt 1090 ms 26164 KB
04_random02.txt 879 ms 16532 KB
04_random03.txt 264 ms 14844 KB
04_random04.txt 273 ms 23420 KB
04_random05.txt 353 ms 23292 KB
04_random06.txt 1205 ms 27128 KB
04_random07.txt 779 ms 30584 KB
04_random08.txt 610 ms 28156 KB
04_random09.txt 431 ms 26620 KB
04_random10.txt 1179 ms 22968 KB
04_random11.txt 1893 ms 45308 KB
04_random12.txt 1957 ms 46204 KB
04_random13.txt 1788 ms 45900 KB
04_rp01.txt 1856 ms 35580 KB
04_rp02.txt 1832 ms 35576 KB
04_rp03.txt 1920 ms 37116 KB
04_rp04.txt 1825 ms 36316 KB
04_rp05.txt 1776 ms 34812 KB
04_rp06.txt 1800 ms 34812 KB
04_rp07.txt 1781 ms 34812 KB
04_rp08.txt 1851 ms 36700 KB
04_rp09.txt 1924 ms 37116 KB
04_rp10.txt 1968 ms 37116 KB
sample_1.txt 7 ms 1788 KB
sample_2.txt 7 ms 1788 KB
sample_3.txt 7 ms 1788 KB