#436884 (Lua) No.9 モンスターのレベル上げ

提出ソース

結果

問題	No.9 モンスターのレベル上げ
ユーザー	👑 obakyan
提出日時	2020-03-01 13:38:15
言語	Lua (LuaJit 2.1.1696795921)
結果	AC
実行時間	2,196 ms / 5,000 ms
コード長	6,111 bytes
コンパイル時間	168 ms
コンパイル使用メモリ	6,948 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-13 20:36:21
合計ジャッジ時間	19,613 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	3 ms 6,816 KB
testcase_02	AC	2,196 ms 6,820 KB
testcase_03	AC	1,731 ms 6,816 KB
testcase_04	AC	921 ms 6,816 KB
testcase_05	AC	606 ms 6,816 KB
testcase_06	AC	206 ms 6,816 KB
testcase_07	AC	12 ms 6,816 KB
testcase_08	AC	272 ms 6,816 KB
testcase_09	AC	2,067 ms 6,820 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	1,941 ms 6,820 KB
testcase_12	AC	1,226 ms 6,816 KB
testcase_13	AC	1,290 ms 6,816 KB
testcase_14	AC	2,034 ms 6,816 KB
testcase_15	AC	1,909 ms 6,816 KB
testcase_16	AC	52 ms 6,820 KB
testcase_17	AC	1,206 ms 6,820 KB
testcase_18	AC	1,056 ms 6,816 KB
testcase_19	AC	33 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

local mma = math.max
local mfl, mce, mmi = math.floor, math.ceil, math.min

local AvlTree = {}
AvlTree.save = function(self, n)
  self.svroot = self.root
  self.box = {}
  for i = 1, n + 1 do
    self.svv[i], self.svp[i] = self.v[i], self.p[i]
    self.svlc[i], self.svrc[i] = self.lc[i], self.rc[i]
    self.svl[i], self.svr[i] = self.l[i], self.r[i]
  end
end
AvlTree.load = function(self, n)
  self.root = self.svroot
  self.box = {}
  for i = 1, n + 1 do
    self.v[i], self.p[i] = self.svv[i], self.svp[i]
    self.lc[i], self.rc[i] = self.svlc[i], self.svrc[i]
    self.l[i], self.r[i] = self.svl[i], self.svr[i]
  end
end

AvlTree.makenode = function(self, val, parent)
  local i = self.box[#self.box]
  table.remove(self.box)
  self.v[i], self.p[i] = val, parent
  self.lc[i], self.rc[i], self.l[i], self.r[i] = 0, 0, 1, 1
  return i
end
AvlTree.clear = function(self, n)
  self.root = 1
  self.box = {}
  for i = n + 1, 2, -1 do table.insert(self.box, i) end
  self.svv, self.svlc, self.svrc, self.svl, self.svr, self.svp = {}, {}, {}, {}, {}, {}
  -- value, leftCount, rightCount, left, right, parent
  self.v, self.lc, self.rc, self.l, self.r, self.p = {}, {}, {}, {}, {}, {}
  for i = 1, n + 1 do
    self.v[i], self.p[i] = 0, 1
    self.lc[i], self.rc[i], self.l[i], self.r[i] = 0, 0, 1, 1
  end
end
AvlTree.create = function(self, lessthan, n)
  self.lessthan = lessthan
  self:clear(n)
end

AvlTree.recalcCount = function(self, i)
  if 1 < i then
    local kl, kr = self.l[i], self.r[i]
    if 1 < kl then self.lc[i] = 1 + mma(self.lc[kl], self.rc[kl])
    else self.lc[i] = 0
    end
    if 1 < kr then self.rc[i] = 1 + mma(self.lc[kr], self.rc[kr])
    else self.rc[i] = 0
    end
  end
end
AvlTree.recalcCountAll = function(self, i)
  while 1 < i do
    self:recalcCount(i)
    i = self.p[i]
  end
end

AvlTree.rotR = function(self, child, parent)
  local granp = self.p[parent]
  self.r[child], self.l[parent] = parent, self.r[child]
  self.p[child], self.p[parent] = granp, child
  self.p[self.l[parent]] = parent
  if 1 < granp then
    if self.l[granp] == parent then
      self.l[granp] = child
    else
      self.r[granp] = child
    end
  else
    self.root = child
  end
  self:recalcCountAll(parent)
end

AvlTree.rotL = function(self, child, parent)
  local granp = self.p[parent]
  self.l[child], self.r[parent] = parent, self.l[child]
  self.p[child], self.p[parent] = granp, child
  self.p[self.r[parent]] = parent
  if 1 < granp then
    if self.r[granp] == parent then
      self.r[granp] = child
    else
      self.l[granp] = child
    end
  else
    self.root = child
  end
  self:recalcCountAll(parent)
end

AvlTree.push = function(self, val)
  if self.root <= 1 then self.root = self:makenode(val, 1) return end
  local pos = self.root
  while true do
    if self.lessthan(val, self.v[pos]) then
      if 1 < self.l[pos] then
        pos = self.l[pos]
      else
        self.l[pos] = self:makenode(val, pos)
        pos = self.l[pos]
        break
      end
    else
      if 1 < self.r[pos] then
        pos = self.r[pos]
      else
        self.r[pos] = self:makenode(val, pos)
        pos = self.r[pos]
        break
      end
    end
  end
  while 1 < pos do
    local child, parent = pos, self.p[pos]
    if parent <= 1 then
      break
    end
    self:recalcCount(parent)
    local lcp_m_rcp = self.lc[parent] - self.rc[parent]
    if lcp_m_rcp % 2 ~= 0 then -- 1 or -1
      pos = parent
    elseif lcp_m_rcp == 2 then
      if self.lc[child] - 1 == self.rc[child] then
        self:rotR(child, parent)
      else
        local cr = self.r[child]
        self:rotL(cr, child)
        self:rotR(cr, parent)
      end
      pos = 1
    elseif lcp_m_rcp == -2 then
      if self.rc[child] - 1 == self.lc[child] then
        self:rotL(child, parent)
      else
        local cl = self.l[child]
        self:rotR(cl, child)
        self:rotL(cl, parent)
      end
      pos = 1
    else
      pos = 1
    end
  end
end

AvlTree.rmsub = function(self, node)
  while 1 < node do
    self:recalcCount(node)
    if self.lc[node] == self.rc[node] then
      node = self.p[node]
    elseif self.lc[node] + 1 == self.rc[node] then
      self:recalcCountAll(self.p[node])
      node = 1
    else
      if self.lc[self.r[node]] == self.rc[self.r[node]] then
        self:rotL(self.r[node], node)
        node = 1
      elseif self.lc[self.r[node]] + 1 == self.rc[self.r[node]] then
        local nr = self.r[node]
        self:rotL(nr, node)
        node = nr
      else
        local nrl = self.l[self.r[node]]
        self:rotR(nrl, self.r[node])
        self:rotL(nrl, node)
        node = nrl
      end
    end
  end
end

AvlTree.pop = function(self)
  local node = self.root
  while 1 < self.l[node] do
    node = self.l[node]
  end
  local v = self.v[node]
  local kp = self.p[node]
  self.p[self.r[node]] = kp
  if 1 < kp then
    self.l[kp] = self.r[node]
    self:rmsub(kp)
  else
    self.root = self.r[node]
  end
  table.insert(self.box, node)
  return v
end

AvlTree.new = function(lessthan, n)
  local obj = {}
  setmetatable(obj, {__index = AvlTree})
  obj:create(lessthan, n)
  return obj
end

local n = io.read("*n", "*l")
local a, b = {}, {}
do
  local s = io.read()
  for g in s:gmatch("%d+") do table.insert(a, tonumber(g)) end
  s = io.read()
  for g in s:gmatch("%d+") do table.insert(b, tonumber(g)) end
end
local val, used = {}, {}
local function initialize()
  for i = 1, n do
    val[i] = a[i]
    used[i] = 0
  end
end
initialize()
local function ltfunc(x, y)
  if val[x] == val[y] then
    return used[x] < used[y]
  else
    return val[x] < val[y]
  end
end
local avl = AvlTree.new(ltfunc, n)
for i = 1, n do avl:push(i) end
avl:save(n)

local ret = 0
for boffset = 0, n - 1 do
  initialize()
  avl:load(n)
  for i = 1, n do
    local bp = i + boffset
    if n < bp then bp = bp - n end
    local apos = avl:pop()
    used[apos] = used[apos] + 1
    val[apos] = val[apos] + mfl(b[bp] / 2)
    avl:push(apos)
  end
  local max = used[1]
  for i = 2, n do
    max = mma(max, used[i])
  end
  ret = boffset == 0 and max or mmi(max, ret)
end
print(ret)

yukicoder

結果

テストケース

ソースコード