結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:27:56 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 577 ms / 3,000 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 11,815 ms |
コンパイル使用メモリ | 296,952 KB |
実行使用メモリ | 36,092 KB |
最終ジャッジ日時 | 2024-08-25 15:28:14 |
合計ジャッジ時間 | 17,035 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
read_line.to_i.times doputs solve()enddef solven, m = read_line.split.map(&.to_i)s = read_line.charsr = manacher(s)max = 0(n * 2).times do |i|if i % 2 == 1len = (r[i] + 1) // 2max = {max, len * 2 - 1}.maxelselen = r[i] // 2max = {max, len * 2}.maxendendreturn 1 if m <= maxr = manacher(s + s)max = 0rep = false(n * 4).times do |i|next if !(i - r[i] <= 2 * n && 2 * n <= i + r[i])if i % 2 == 1len = (r[i] + 1) // 2if len * 2 - 1 > maxmax = len * 2 - 1rem = s[..(i // 2 - len)]if rem == rem.reverserep = trueendendelselen = r[i] // 2if len * 2 > maxmax = len * 2rem = s[..(i // 2 - 1 - len)]if rem == rem.reverserep = trueendendendend# puts [r, max, rep]return 2 if m <= maxr = manacher(s + s + s)max3 = 0(n * 6).times do |i|if i % 2 == 1len = (r[i] + 1) // 2max3 = {max3, len * 2 - 1}.maxelselen = r[i] // 2max3 = {max3, len * 2}.maxendendif max3 == max + n(m - max + n - 1) // n + 2else-1endenddef manacher(s)str = ['$']s.each do |c|str << c << '$'endi = 0j = 0rad = Array.new(str.size, 0)while i < str.sizewhile i - j >= 0 && i + j < str.size && str[i - j] == str[i + j]j += 1endrad[i] = jk = 1while k <= i && k + rad[i - k] < jrad[i + k] = rad[i - k]k += 1endi += kj -= kendrad# pos = 1.step(to: str.size - 1, by: 2).max_by { |i| rad[i] }# len = (rad[pos] + 1) // 2# odd_max = {(pos - rad[pos] + 1) // 2, len * 2 - 1}# pos = 0.step(to: str.size - 1, by: 2).max_by { |i| rad[i] }# len = rad[pos] // 2# even_max = {(pos - rad[pos] + 1) // 2, len * 2}end