#757714 (Lua) No.1894 Delete AB

• 問題: No.1894 Delete AB
• ユーザー: 👑 obakyan
• 提出日時: 2022-05-02 15:32:03
• 言語: Lua (LuaJit 2.1.1696795921)
• 結果: WA
• 実行時間: -
• コード長: 8,276 bytes
• コンパイル時間: 118 ms
• コンパイル使用メモリ: 6,944 KB
• 実行使用メモリ: 18,688 KB
• 最終ジャッジ日時: 2024-07-01 19:16:26
• 合計ジャッジ時間: 2,468 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	15 ms; 6,940 KB
testcase_14	AC	72 ms; 18,688 KB

ソースコード

local function SA_IS(data, data_size, word_size)
  local suffix_array = {}
  local type_tag = {} -- -2: L, -1: S, 1~: i-th LMS
  for i = 1, data_size do
    suffix_array[i] = -1
    type_tag[i] = -2
  end
  local word_count = {}
  local word_count_sum = {}
  local word_pushback_count = {}
  local word_pushfront_count = {}
  for i = 1, word_size do
    word_count[i] = 0
    word_count_sum[i] = 0
    word_pushback_count[i] = 0
    word_pushfront_count[i] = 0
  end
  local lms_count = 0
  local lms_data_indexes = {}
  local sorted_lms_data_indexes = {}
  local lms_compressed_data = {}

  for i = 1, data_size do
    word_count[data[i]] = word_count[data[i]] + 1
  end
  word_count_sum[1] = word_count[1]
  for i = 2, word_size do
    word_count_sum[i] = word_count_sum[i - 1] + word_count[i]
  end
  local prev_type = -2
  for i = data_size - 1, 1, -1 do
    if data[i] == data[i + 1] then
      type_tag[i] = prev_type
    else
      type_tag[i] = data[i] < data[i + 1] and -1 or -2
      prev_type = type_tag[i]
    end
  end
  for i = 2, data_size do
    if type_tag[i - 1] == -2 and type_tag[i] == -1 then
      lms_count = lms_count + 1
      type_tag[i] = lms_count
      lms_data_indexes[lms_count] = i
      sorted_lms_data_indexes[lms_count] = -1
      lms_compressed_data[lms_count] = -1
    end
  end
  -- put LMS
  for i = 1, lms_count do
    local idx = lms_data_indexes[i]
    local w = data[idx]
    suffix_array[word_count_sum[w] - word_pushback_count[w]] = idx
    word_pushback_count[w] = word_pushback_count[w] + 1
  end
  -- put L
  do
    local w = data[data_size]
    local offset = w == 1 and 0 or word_count_sum[w - 1]
    suffix_array[offset + 1] = data_size
    word_pushfront_count[w] = word_pushfront_count[w] + 1
  end
  for sufa_idx = 1, data_size - 1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if type_tag[data_idx] == -2 then
        local w = data[data_idx]
        local offset = w == 1 and 0 or word_count_sum[w - 1]
        word_pushfront_count[w] = word_pushfront_count[w] + 1
        suffix_array[offset + word_pushfront_count[w]] = data_idx
      end
    end
  end
  -- remove LMS
  for w = 1, word_size do
    word_pushback_count[w] = 0
  end
  -- put S
  for sufa_idx = data_size, 1, -1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if -1 <= type_tag[data_idx] then
        local w = data[data_idx]
        suffix_array[word_count_sum[w] - word_pushback_count[w]] = data_idx
        word_pushback_count[w] = word_pushback_count[w] + 1
      end
    end
  end
  local lms_data_value = 0
  local prev_lms_index = 0
  local prev_lms_data_index = 0
  for sufa_idx = 1, data_size do
    local data_idx = suffix_array[sufa_idx]
    local lms_idx = type_tag[data_idx]
    if 1 <= lms_idx then
      local is_same = false
      if 0 < prev_lms_data_index and prev_lms_index ~= lms_count and lms_idx ~= lms_count then
        local len1 = lms_data_indexes[lms_idx + 1] - data_idx
        local len2 = lms_data_indexes[prev_lms_index + 1] - prev_lms_data_index
        if len1 == len2 then
          is_same = true
          for i = 0, len1 do
            if data[i + data_idx] ~= data[i + prev_lms_data_index] then
              is_same = false
              break
            end
          end
        end
      end
      if not is_same then
        lms_data_value = lms_data_value + 1
      end
      lms_compressed_data[lms_idx] = lms_data_value
      prev_lms_index = lms_idx
      prev_lms_data_index = data_idx
    end
  end
  if lms_data_value == lms_count then
    for i = 1, lms_count do
      sorted_lms_data_indexes[lms_compressed_data[i]] = lms_data_indexes[i]
    end
  else
    local lms_sa = SA_IS(lms_compressed_data, lms_count, lms_data_value)
    for i = 1, lms_count do
      sorted_lms_data_indexes[i] = lms_data_indexes[lms_sa[i]]
    end
  end
  for i = 1, lms_count do
    local inv = lms_count + 1 - i
    if inv <= i then break end
    sorted_lms_data_indexes[i], sorted_lms_data_indexes[inv]
      = sorted_lms_data_indexes[inv], sorted_lms_data_indexes[i]
  end
  -- Second Induced Sort
  for i = 1, data_size do
    suffix_array[i] = -1
  end
  for i = 1, word_size do
    word_pushback_count[i] = 0
    word_pushfront_count[i] = 0
  end
  -- put LMS
  for i = 1, lms_count do
    local idx = sorted_lms_data_indexes[i]
    local w = data[idx]
    suffix_array[word_count_sum[w] - word_pushback_count[w]] = idx
    word_pushback_count[w] = word_pushback_count[w] + 1
  end
  -- put L
  do
    local w = data[data_size]
    local offset = w == 1 and 0 or word_count_sum[w - 1]
    suffix_array[offset + 1] = data_size
    word_pushfront_count[w] = word_pushfront_count[w] + 1
  end
  for sufa_idx = 1, data_size - 1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if type_tag[data_idx] == -2 then
        local w = data[data_idx]
        local offset = w == 1 and 0 or word_count_sum[w - 1]
        word_pushfront_count[w] = word_pushfront_count[w] + 1
        suffix_array[offset + word_pushfront_count[w]] = data_idx
      end
    end
  end
  -- remove LMS
  for w = 1, word_size do
    word_pushback_count[w] = 0
  end
  -- put S
  for sufa_idx = data_size, 1, -1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if -1 <= type_tag[data_idx] then
        local w = data[data_idx]
        suffix_array[word_count_sum[w] - word_pushback_count[w]] = data_idx
        word_pushback_count[w] = word_pushback_count[w] + 1
      end
    end
  end
  return suffix_array
end

local SAIS = {}
SAIS.create = function(self, data, data_size, word_size)
  local sufa = SA_IS(data, data_size, word_size)
  local sufa_inv = {}
  for i = 1, data_size do sufa_inv[i] = 0 end
  for i = 1, data_size do
    sufa_inv[sufa[i]] = i
  end
  self.sufa = sufa
  self.sufa_inv = sufa_inv
  -- LCPA
  local n = data_size
  local lcpa = {}
  for i = 1, n - 1 do lcpa[i] = 0 end
  local spos = 0
  for i = 1, n do
    local lcppos = 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 data[p1] == data[p2] then
          len = len + 1
          p1, p2 = p1 + 1, p2 + 1
        else break
        end
      end
      lcpa[lcppos] = len
      spos = 1 < len and len - 1 or 0
    end
  end
  self.lcpa = lcpa
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
--experimental
SAIS.lowerBound = function(self, s)
  if tblcomp(s, self.data, self.sufa[1]) then
    return 1
  end
  if not tblcomp(s, self.data, self.sufa[self.n]) then
    return self.n + 1
  end
  local min, max = 1, self.n
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if tblcomp(s, self.data, self.sufa[mid]) then
      max = mid
    else
      min = mid
    end
  end
  return max
end

local q = io.read("*n", "*l")
for iq = 1, q do
  local n = io.read("*n", "*l")
  local s = io.read()
  local t = {}
  local need_add = false
  for i = 1, n do
    local b = s:byte(i) - 64
    if b == 1 then
      if need_add then
        table.insert(t, 1)
        table.insert(t, 2)
        need_add = false
      end
      table.insert(t, 1)
    else
      if t[#t] == 1 then
        table.remove(t)
        need_add = true
      else
        if need_add then
          table.insert(t, 1)
          table.insert(t, 2)
          need_add = false
        end
        table.insert(t, 2)
      end
    end
  end
  if need_add then
    table.insert(t, 1)
    table.insert(t, 2)
  end
  n = #t
  local ret = {}
  SAIS:create(t, n, 2)
  local pos = 1
  while pos <= n do
    if t[pos] == 1 then
      if pos + 2 <= n and SAIS.sufa_inv[pos] < SAIS.sufa_inv[pos + 2] then
        pos = pos + 2
      else
        table.insert(ret, "A")
        pos = pos + 1
      end
    else
      table.insert(ret, "B")
      pos = pos + 1
    end
  end
  print(table.concat(ret))
end