#712134 (Ruby) No.1650 Moving Coins

• 問題: No.1650 Moving Coins
• ユーザー: 小野寺健
• 提出日時: 2021-11-01 12:51:39
• 言語: Ruby (3.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 571 bytes
• コンパイル時間: 60 ms
• コンパイル使用メモリ: 7,680 KB
• 実行使用メモリ: 58,240 KB
• 最終ジャッジ日時: 2024-04-18 07:55:56
• 合計ジャッジ時間: 16,011 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	85 ms; 19,232 KB
testcase_01	AC	91 ms; 20,096 KB
testcase_02	AC	84 ms; 12,288 KB
testcase_03	AC	353 ms; 40,576 KB
testcase_04	AC	265 ms; 37,504 KB
testcase_05	AC	314 ms; 40,576 KB
testcase_06	AC	368 ms; 42,240 KB
testcase_07	AC	372 ms; 44,160 KB
testcase_08	AC	465 ms; 55,936 KB
testcase_09	AC	1,175 ms; 50,688 KB
testcase_10	AC	472 ms; 58,240 KB
testcase_11	AC	541 ms; 55,680 KB
testcase_12	AC	549 ms; 44,160 KB
testcase_13	AC	558 ms; 43,008 KB
testcase_14	AC	562 ms; 55,552 KB
testcase_15	AC	445 ms; 43,888 KB
testcase_16	AC	517 ms; 57,728 KB
testcase_17	AC	501 ms; 56,960 KB
testcase_18	AC	554 ms; 53,124 KB
testcase_19	TLE	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-

コンパイルメッセージ

Syntax OK

ソースコード

N = gets.to_i
A = gets.split(" ").map{|s| s.to_i}
B = gets.split(" ").map{|s| s.to_i}

q = []
c = Array.new((A+B).max, false)
0.upto(N-1) {|i|
	a, b = A[i], B[i]
	c[a-1] = true
	q << [i+1, a-1, b-a] if a != b
}

ans = []

while q.length > 0 do
	i, pos, diff = q.shift
	d = diff > 0 ? 1 : -1
	if c[pos+d] then
		q << [i, pos, diff]
	else
		c[pos] = false
		while diff != 0 and (not c[pos+d]) do
			diff -= d
			pos += d
			ans << [i, d > 0 ? "R" : "L"]
		end
		c[pos] = true
		q << [i, pos, diff] if diff != 0
	end
end

puts ans.length
ans.each {|i, d|
	puts "#{i} #{d}"
}