結果

問題 No.1859 ><<<
ユーザー 👑 obakyanobakyan
提出日時 2022-03-20 00:54:47
言語 Lua
(LuaJit 2.1.1696795921)
結果
TLE  
実行時間 -
コード長 5,252 bytes
コンパイル時間 134 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 137,764 KB
最終ジャッジ日時 2024-10-05 13:55:44
合計ジャッジ時間 24,549 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1,680 ms
137,764 KB
testcase_05 AC 1,650 ms
130,176 KB
testcase_06 AC 1,616 ms
130,232 KB
testcase_07 AC 1,700 ms
130,224 KB
testcase_08 AC 1,641 ms
132,124 KB
testcase_09 AC 1,622 ms
130,076 KB
testcase_10 AC 373 ms
19,584 KB
testcase_11 AC 1,827 ms
66,488 KB
testcase_12 AC 1,480 ms
63,680 KB
testcase_13 AC 756 ms
33,348 KB
testcase_14 AC 1,816 ms
63,680 KB
testcase_15 TLE -
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mmi, mma = math.min, math.max
local mfl, mce = math.floor, math.ceil
local TSufA = {}
TSufA.makeSufA = function(self)
  self.sufa = {}
  local n = #self.str
  local idx, tbl1, tbl2 = self.sufa, {}, {}
  local tmp_tbl = {}
  for i = 1, n do
    idx[i] = i
    tbl1[i] = self.str[i]
    -- tbl1[i] = self.str:sub(i, i):byte() - 95 -- "a" = 97
    tbl2[i] = 0
    tmp_tbl[i] = 0
  end
  idx[n + 1], tbl1[n + 1], tbl2[n + 1] = n + 1, 1, 0
  n = n + 1 -- add empty to last
  table.sort(idx, function(a, b) return tbl1[a] < tbl1[b] end)
  local step, stepflag = 1, true
  while step < n do
    local v = stepflag and tbl1 or tbl2
    local vd = stepflag and tbl2 or tbl1
    stepflag = not stepflag
    local stepdst = {}
    for i = 1, n do
      local dst = i + step
      if n < dst then dst = dst - n end
      stepdst[i] = dst
    end
    local left, major = 1, v[idx[1]]
    local minor_min = v[stepdst[idx[1]]]
    local minor_max = minor_min
    local minormap = {}
    local cur = 0
    for i = 1, n do
      local minor = v[stepdst[idx[i]]]
      if minormap[minor] then minormap[minor] = minormap[minor] + 1
      else minormap[minor] = 1
      end
      minor_min, minor_max = mmi(minor_min, minor), mma(minor_max, minor)
      local isend = i == n or major ~= v[idx[i + 1]]
      if isend then
        local right = i
        if left == right then
          cur = cur + 1
          vd[idx[left]] = cur
        elseif minor_min ~= minor_max then
          local minortbl = {}
          for k, _u in pairs(minormap) do table.insert(minortbl, k) end
          table.sort(minortbl)
          local offset = 0
          for i = 1, #minortbl do
            local cnt = minormap[minortbl[i]]
            minormap[minortbl[i]] = i
            minortbl[i] = offset -- reuse
            offset = offset + cnt
          end
          for j = left, right do
            local idxj = idx[j]
            local minor_idx = minormap[v[stepdst[idxj]]]
            local ofst = minortbl[minor_idx]
            ofst = ofst + 1
            minortbl[minor_idx] = ofst
            tmp_tbl[ofst] = idxj
            vd[idxj] = cur + minor_idx
          end
          cur = cur + #minortbl
          for j = left, right do
            idx[j] = tmp_tbl[j - left + 1]
          end
        else
          cur = cur + 1
          for j = left, right do
            vd[idx[j]] = cur
          end
        end
        if i < n then
          left, major = i + 1, v[idx[i + 1]]
          minor_min = v[stepdst[idx[i + 1]]]
          minor_max = minor_min
          minormap = {}
        end
      end
    end
    step = step * 2
  end
  -- remove empty from first (O(N))
  table.remove(self.sufa, 1)
  n = n - 1
  self.sufa_inv = {}
  for i = 1, n do self.sufa_inv[i] = 0 end
  for i = 1, n do
    self.sufa_inv[self.sufa[i]] = i
  end
end
TSufA.makeLCPA = function(self)
  assert(self.sufa)
  local n = #self.sufa
  self.lcpa = {}
  local str, sufa, lcpa = self.str, self.sufa, self.lcpa
  for i = 1, n - 1 do lcpa[i] = 0 end
  local spos = 0
  for i = 1, n do
    local lcppos = self.sufa_inv[i]
    if lcppos < n then
      local len = spos
      local p1, p2 = sufa[lcppos], sufa[lcppos + 1]
      p1, p2 = p1 + spos, p2 + spos
      while p1 <= n and p2 <= n do
        if str[p1] == str[p2] then
          len = len + 1
          p1, p2 = p1 + 1, p2 + 1
        else break
        end
      end
      lcpa[lcppos] = len
      spos = mma(0, len - 1)
    end
  end
end

local function tblcomp(a, b, bspos)
-- return a <= b:sub(bspos, #b)
  local lim = mmi(#a, #b - bspos + 1)
  for i = 1, lim do
    if a[i] ~= b[bspos + i - 1] then
      return a[i] < b[bspos + i - 1] and true or false
    end
  end
  return #a <= #b - bspos + 1
end

TSufA.lowerBound = function(self, s)
  if tblcomp(s, self.str, self.sufa[1]) then
    return 1
  end
  if not tblcomp(s, self.str, self.sufa[#self.str]) then
    return #self.str + 1
  end
  local min, max = 1, #self.str
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if tblcomp(s, self.str, self.sufa[mid]) then
      max = mid
    else
      min = mid
    end
  end
  return max
end

TSufA.create = function(self, str)
  self.str = str
  self:makeSufA()
  self:makeLCPA()
end

TSufA.new = function(str)
  local obj = {}
  setmetatable(obj, {__index = TSufA})
  obj:create(str)
  return obj
end

local n = io.read("*n")
local a = {}
for i = 1, n do
  a[i] = io.read("*n")
end
io.read()
local t = {}
for i = 1, n - 1 do
  if a[i] < a[i + 1] then
    t[i] = 3
  else
    t[i] = 2
  end
end
if a[n] < a[1] then
  t[n] = 3
else
  t[n] = 2
end
for i = 1, n - 2 do
  t[n + i] = t[i]
end
-- t = table.concat(t)

local sa = TSufA.new(t)
-- print(os.clock())
local s = io.read()
local z = {}
for i = 1, n - 1 do
  z[i] = s:sub(i, i) == "<" and 3 or 2
end
local lb = sa:lowerBound(z)
-- print(lb, table.concat(sa.sufa, " "), t)
if #t < lb then
  print(-1)
  os.exit()
end
local pos = sa.sufa[lb]
if n < pos then print(-1) os.exit() end
for i = 1, n - 1 do
  if z[i] ~= t[pos + i - 1] then
    print(-1) os.exit()
  end
end
local cand = pos
while true do
  if lb <= 2 * n - 4 and n - 1 <= sa.lcpa[lb] then
    lb = lb + 1
    cand = mmi(cand, sa.sufa[lb])
  else
    break
  end
end
print(cand - 1)
-- print(os.clock())
0