結果
問題 | No.1646 Avoid Palindrome |
ユーザー | yuruhiya |
提出日時 | 2021-08-13 21:42:12 |
言語 | Crystal (1.14.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 11,585 bytes |
コンパイル時間 | 13,359 ms |
コンパイル使用メモリ | 295,600 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-11-08 15:04:51 |
合計ジャッジ時間 | 28,341 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 674 ms
5,248 KB |
testcase_05 | AC | 669 ms
5,248 KB |
testcase_06 | AC | 637 ms
5,248 KB |
testcase_07 | AC | 653 ms
5,248 KB |
testcase_08 | AC | 656 ms
5,248 KB |
testcase_09 | AC | 622 ms
5,248 KB |
testcase_10 | AC | 639 ms
5,248 KB |
testcase_11 | AC | 632 ms
5,248 KB |
testcase_12 | AC | 668 ms
5,248 KB |
testcase_13 | AC | 663 ms
5,248 KB |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | AC | 341 ms
5,248 KB |
testcase_30 | AC | 339 ms
5,248 KB |
testcase_31 | AC | 336 ms
5,248 KB |
testcase_32 | AC | 346 ms
5,248 KB |
testcase_33 | AC | 341 ms
5,248 KB |
testcase_34 | TLE | - |
testcase_35 | AC | 3 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 2 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 338 ms
5,248 KB |
ソースコード
# require "/template"# require "./tuple/times"struct Tupledef times(&block) : Nil{% begin %}{% for i in 0...@type.size %}{% if @type[i].has_method?(:each) %}self[{{i}}].each do |i{{i}}|{% else %}self[{{i}}].times do |i{{i}}|{% end %}{% end %}yield({% for i in 0...@type.size %} i{{i}}, {% end %}){% for i in 0...@type.size %} end {% end %}{% end %}endprivate class TimesIterator(T)include Iterator(T)def initialize(@n : T)tuple = {% begin %}{ {% for i in 0...T.size %} T[{{i}}].zero, {% end %} }{% end %}@index = tuple.as(T)@first = trueenddef nextif @first@first = falsereturn @indexend{% begin %}{%type = @type.type_vars[0]size = type.size%}{% for i in 1..size %}if @index[{{size - i}}] < @n[{{size - i}}] - 1@index = {{% for j in 0...size %}{% if j < size - i %}@index[{{j}}],{% elsif j == size - i %}@index[{{j}}] + 1,{% else %}{{type[j]}}.zero,{% end %}{% end %}}return @indexend{% end %}stop{% end %}endenddef timesTimesIterator(self).new(self)endend# require "./comparable/min_max"module Comparable(T)def min(x : T)self > x ? x : selfenddef max(x : T)self < x ? x : selfendend# require "./array/new"class Arraydef self.new(sizes : Tuple(*T), initial_value) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { {% end %}initial_value{% for i in 0...T.size %} } {% end %}{% end %}enddef self.new(sizes : Tuple(*T), &block) forall T{% begin %}{% for i in 0...T.size %} Array.new(sizes[{{i}}]) { |index{{i}}| {% end %}yield({% for i in 0...T.size %} index{{i}}, {% end %}){% for i in 0...T.size %} } {% end %}{% end %}endend# require "./array/change"class Array(T)def chmin(i : Int, value : T)(self[i] > value).tap do |f|self[i] = value if fendendprotected def chmin(i : Int, *indexes, value)self[i].chmin(*indexes, value: value)enddef chmin(indexes : Tuple, value)chmin(*indexes, value: value)enddef chmax(i : Int, value : T)(self[i] < value).tap do |f|self[i] = value if fendendprotected def chmax(i : Int, *indexes, value)self[i].chmax(*indexes, value: value)enddef chmax(indexes : Tuple, value)chmax(*indexes, value: value)endend# require "./scanner"# ### Specifications## ```plain# Inside input macro | Expanded code# -------------------------------------+---------------------------------------# Uppercase string: Int32, Int64, etc. | {}.new(Scanner.s)# s | Scanner.s# c | Scanner.c# Other lowercase string: i, i64, etc. | Scanner.s.to_{}# operator[]: type[size] | Array.new(input(size)) { input(type) }# Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)}# Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)]# Range literal: t1..t2 | input(t1)..input(t2)# If: cond ? t1 : t2 | cond ? input(t1) : input(t2)# Assign: target = value | target = input(value)# ```## ### Examples## Input:# ```plain# 5 3# foo bar# 1 2 3 4 5# ```# ```# n, m = input(Int32, Int64) # => {5, 10i64}# input(String, Char[m]) # => {"foo", ['b', 'a', 'r']}# input(Int32[n]) # => [1, 2, 3, 4, 5]# ```# ```# n, m = input(i, i64) # => {5, 10i64}# input(s, c[m]) # => {"foo", ['b', 'a', 'r']}# input(i[n]) # => [1, 2, 3, 4, 5]# ```## Input:# ```plain# 2 3# 1 2 3# 4 5 6# ```## ```# h, w = input(i, i) # => {2, 3}# input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]]# ```# ```# input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]]# ```## Input:# ```plain# 5 3# 3 1 4 2 5# 1 2# 2 3# 3 1# ```# ```# n, m = input(i, i) # => {5, 3}# input(i.pred[n]) # => [2, 0, 3, 1, 4]# input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}]# ```## Input:# ```plain# 3# 1 2# 2 2# 3 2# ```# ```# input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}]# ```## Input:# ```plain# 3# 1 2# 2 3# 3 1# ```# ```# n = input(i)# input_column({Int32, Int32}, n) # => {[1, 2, 3], [2, 3, 1]}# ```class Scannerprivate def self.skip_to_not_spacepeek = STDIN.peeknot_space = peek.index { |x| x != 32 && x != 10 } || peek.sizeSTDIN.skip(not_space)enddef self.cskip_to_not_spaceSTDIN.read_char.not_nil!enddef self.sskip_to_not_spacepeek = STDIN.peekif index = peek.index { |x| x == 32 || x == 10 }STDIN.skip(index + 1)return String.new(peek[0, index])endString.build do |buffer|loop dobuffer.write peekSTDIN.skip(peek.size)peek = STDIN.peekbreak if peek.empty?if index = peek.index { |x| x == 32 || x == 10 }buffer.write peek[0, index]STDIN.skip(index)breakendendendendendmacro internal_input(type, else_ast){% if Scanner.class.has_method?(type.id) %}Scanner.{{type.id}}{% elsif type.stringify == "String" %}Scanner.s{% elsif type.stringify == "Char" %}Scanner.c{% elsif type.stringify =~ /[A-Z][a-z0-9_]*/ %}{{type.id}}.new(Scanner.s){% elsif String.has_method?("to_#{type}".id) %}Scanner.s.to_{{type.id}}{% else %}{{else_ast}}{% end %}endmacro internal_input_array(type, args){% for i in 0...args.size %}%size{i} = input({{args[i]}}){% end %}{% begin %}{% for i in 0...args.size %} Array.new(%size{i}) { {% end %}input({{type.id}}){% for i in 0...args.size %} } {% end %}{% end %}endmacro input(type){% if type.is_a?(Call) %}{% if type.receiver.is_a?(Nop) %}internal_input({{type.name}}, {{type.name}}({% for argument in type.args %} input({{argument}}), {% end %})){% elsif type.name.stringify == "[]" %}internal_input_array({{type.receiver}}, {{type.args}}){% else %}input({{type.receiver}}).{{type.name.id}}({% for argument in type.args %} input({{argument}}), {% end %}) {{type.block}}{% end %}{% elsif type.is_a?(TupleLiteral) %}{ {% for i in 0...type.size %} input({{type[i]}}), {% end %} }{% elsif type.is_a?(ArrayLiteral) %}[ {% for i in 0...type.size %} input({{type[i]}}), {% end %} ]{% elsif type.is_a?(RangeLiteral) %}Range.new(input({{type.begin}}), input({{type.end}}), {{type.excludes_end?}}){% elsif type.is_a?(If) %}{{type.cond}} ? input({{type.then}}) : input({{type.else}}){% elsif type.is_a?(Assign) %}{{type.target}} = input({{type.value}}){% else %}internal_input({{type.id}}, {{type.id}}){% end %}endmacro input(*types){ {% for type in types %} input({{type}}), {% end %} }endmacro input_column(types, size){% for type, i in types %}%array{i} = Array({{type}}).new({{size}}){% end %}{{size}}.times do{% for type, i in types %}%array{i} << input({{type}}){% end %}end{ {% for type, i in types %} %array{i}, {% end %} }end# require "/math/mint"macro static_modint(name, mod)struct {{name}}MOD = {{mod}}i64def self.zeronewenddef self.raw(value : Int64)result = newresult.value = valueresultendmacro [](*nums){% verbatim do %}Array({{@type}}).build({{nums.size}}) do |%buffer|{% for num, i in nums %}%buffer[{{i}}] = {{@type}}.new({{num}}){% end %}{{nums.size}}end{% end %}endgetter value : Int64def initialize@value = 0i64enddef initialize(value)@value = value.to_i64 % MODenddef initialize(m : self)@value = m.valueendprotected def value=(value : Int64)@value = valueenddef ==(m : self)value == m.valueenddef ==(m)value == menddef + : selfselfenddef - : selfself.class.raw(value != 0 ? MOD &- value : 0i64)enddef +(v)self + self.class.new(v)enddef +(m : self)x = value &+ m.valuex &-= MOD if x >= MODself.class.raw(x)enddef -(v)self - self.class.new(v)enddef -(m : self)x = value &- m.valuex &+= MOD if x < 0self.class.raw(x)enddef *(v)self * self.class.new(v)enddef *(m : self)self.class.new(value &* m.value)enddef /(v)self / self.class.new(v)enddef /(m : self)raise DivisionByZeroError.new if m.value == 0a, b, u, v = m.value, MOD, 1i64, 0i64while b != 0t = a // ba &-= t &* ba, b = b, au &-= t &* vu, v = v, uendself.class.new(value &* u)enddef //(v)self / venddef **(exponent : Int)t, res = self, self.class.raw(1i64)while exponent > 0res *= t if exponent & 1 == 1t *= texponent >>= 1endresend{% for op in %w[< <= > >=] %}def {{op.id}}(other)raise NotImplementedError.new({{op}})end{% end %}def invself.class.raw(1) // selfenddef succself.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64)enddef predself.class.raw(value != 0 ? value &- 1 : MOD &- 1)enddef absselfenddef abs2self * selfenddef to_i64 : Int64valueenddelegate to_s, to: @valuedelegate inspect, to: @valueend{% to = ("to_" + name.stringify.downcase.gsub(/mint|modint/, "m")).id %}struct Int{% for op in %w[+ - * / //] %}def {{op.id}}(value : {{name}}){{to}} {{op.id}} valueend{% end %}{% for op in %w[< <= > >=] %}def {{op.id}}(m : {{name}})raise NotImplementedError.new({{op}})end{% end %}def {{to}} : {{name}}{{name}}.new(self)endendclass Stringdef {{to}} : {{name}}{{name}}.new(self)endendendstatic_modint(Mint, 1000000007)static_modint(Mint2, 998244353)n = input(i)s = input(c[n])if n == 1puts s[0] == '?' ? 26 : 1exitenddp = Array.new({26, 26}, 0.to_m2)(0...26).each do |i|next unless s[0] == '?' || s[0] == 'a' + i(0...26).each do |j|next unless s[1] == '?' || s[1] == 'a' + jif i != jdp[i][j] += 1endendends[2..].each do |x|dp2 = Array.new({26, 26}, 0.to_m2)if x == '?'(0...26).each do |i|(0...26).each do |j|next if i == jnext if dp[i][j] == 0(0...26).each do |k|next if i == k || j == kdp2[j][k] += dp[i][j]endendendelse(0...26).each do |i|(0...26).each do |j|next if i == jnext if j == x - 'a'next if i == x - 'a'dp2[j][x - 'a'] += dp[i][j]endendenddp = dp2endputs dp.sum(&.sum)