#733421 (Lua) No.1816 MUL-DIV Game

提出ソース

結果

問題	No.1816 MUL-DIV Game
ユーザー	obakyan
提出日時	2022-01-22 11:26:26
言語	Lua (LuaJit 2.1.1696795921)
結果	AC
実行時間	490 ms / 2,000 ms
コード長	13,182 bytes
コンパイル時間	144 ms
コンパイル使用メモリ	5,248 KB
実行使用メモリ	19,456 KB
最終ジャッジ日時	2024-05-05 10:18:00
合計ジャッジ時間	5,322 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	11 ms 5,376 KB
testcase_11	AC	11 ms 5,376 KB
testcase_12	AC	8 ms 5,376 KB
testcase_13	AC	257 ms 11,392 KB
testcase_14	AC	142 ms 11,264 KB
testcase_15	AC	190 ms 12,032 KB
testcase_16	AC	56 ms 5,888 KB
testcase_17	AC	371 ms 19,380 KB
testcase_18	AC	340 ms 19,456 KB
testcase_19	AC	166 ms 11,520 KB
testcase_20	AC	384 ms 19,164 KB
testcase_21	AC	127 ms 7,808 KB
testcase_22	AC	100 ms 7,424 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	473 ms 19,336 KB
testcase_26	AC	23 ms 5,376 KB
testcase_27	AC	490 ms 19,200 KB
testcase_28	AC	24 ms 5,376 KB
testcase_29	AC	451 ms 19,052 KB

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

ソースコード

raw source code

local mfl, mce = math.floor, math.ceil
local band, bor = bit.band, bit.bor

local rb_bitmask_size = 30
local rb_bitmask = {1}
for i = 2, rb_bitmask_size do
  rb_bitmask[i] = rb_bitmask[i - 1] * 2
end

local RBTree = {}
RBTree.initColor = function(self, max_node_count)
  local a = mce(max_node_count / rb_bitmask_size)
  for i = 1, a do self.colors[i] = 0 end
end
RBTree.isRed = function(self, node_idx)
  local a = mce(node_idx / rb_bitmask_size)
  local b = node_idx - (a - 1) * rb_bitmask_size
  return 0 < band(self.colors[a], rb_bitmask[b])
end
RBTree.setRed = function(self, node_idx)
  local a = mce(node_idx / rb_bitmask_size)
  local b = node_idx - (a - 1) * rb_bitmask_size
  self.colors[a] = bit.bor(self.colors[a], rb_bitmask[b])
end
RBTree.setBlack = function(self, node_idx)
  local a = mce(node_idx / rb_bitmask_size)
  local b = node_idx - (a - 1) * rb_bitmask_size
  if 0 < band(self.colors[a], rb_bitmask[b]) then
    self.colors[a] = self.colors[a] - rb_bitmask[b]
  end
end
RBTree.rotateL = function(self, idx, right_idx)
  local l, r = self.l, self.r
  local k, v, w = self.key, self.value, self.w
  r[idx], r[right_idx], l[right_idx], l[idx] = r[right_idx], l[right_idx], l[idx], right_idx
  k[idx], k[right_idx] = k[right_idx], k[idx]
  v[idx], v[right_idx] = v[right_idx], v[idx]
  if 0 < r[idx] then w[right_idx] = w[right_idx] - w[r[idx]] end
  if 0 < l[right_idx] then w[right_idx] = w[right_idx] + w[l[right_idx]] end
end
RBTree.rotateR = function(self, idx, left_idx)
  local l, r = self.l, self.r
  local k, v, w = self.key, self.value, self.w
  l[idx], l[left_idx], r[left_idx], r[idx] = l[left_idx], r[left_idx], r[idx], left_idx
  k[idx], k[left_idx] = k[left_idx], k[idx]
  v[idx], v[left_idx] = v[left_idx], v[idx]
  if 0 < l[idx] then w[left_idx] = w[left_idx] - w[l[idx]] end
  if 0 < r[left_idx] then w[left_idx] = w[left_idx] + w[r[left_idx]] end
end
RBTree.rotateLR = function(self, idx, left_idx, leftright_idx)
  local l, r = self.l, self.r
  local k, v, w = self.key, self.value, self.w
  r[left_idx], l[leftright_idx], r[leftright_idx], r[idx] = l[leftright_idx], r[leftright_idx], r[idx], leftright_idx
  k[idx], k[leftright_idx] = k[leftright_idx], k[idx]
  v[idx], v[leftright_idx] = v[leftright_idx], v[idx]
  if 0 < l[leftright_idx] then
    w[left_idx] = w[left_idx] - 1 - w[l[leftright_idx]]
  else
    w[left_idx] = w[left_idx] - 1
  end
  if 0 < r[leftright_idx] then w[leftright_idx] = w[leftright_idx] + w[r[leftright_idx]] end
  if 0 < r[left_idx] then w[leftright_idx] = w[leftright_idx] - w[r[left_idx]] end
end
RBTree.rotateRL = function(self, idx, right_idx, rightleft_idx)
  local l, r = self.l, self.r
  local k, v, w = self.key, self.value, self.w
  l[right_idx], r[rightleft_idx], l[rightleft_idx], l[idx] = r[rightleft_idx], l[rightleft_idx], l[idx], rightleft_idx
  k[idx], k[rightleft_idx] = k[rightleft_idx], k[idx]
  v[idx], v[rightleft_idx] = v[rightleft_idx], v[idx]
  if 0 < r[rightleft_idx] then
    w[right_idx] = w[right_idx] - 1 - w[r[rightleft_idx]]
  else
    w[right_idx] = w[right_idx] - 1
  end
  if 0 < l[rightleft_idx] then w[rightleft_idx] = w[rightleft_idx] + w[l[rightleft_idx]] end
  if 0 < l[right_idx] then w[rightleft_idx] = w[rightleft_idx] - w[l[right_idx]] end
end
RBTree.create = function(self, max_node_count, lt)
  self.lt = lt
  if not lt then self.lt = function(a, b) return a < b end end
  self.node_count = 0
  self.root = 0
  self.free_nodes = {}
  for i = 1, max_node_count do self.free_nodes[i] = i end
  self.l, self.r, self.key, self.value = {}, {}, {}, {}
  self.w = {}
  self.colors = {}
  self:initColor(max_node_count)
end
RBTree.push = function(self, key, value)
  assert(value ~= nil)
  local node_idxes_by_rank = {}
  local cur_idx = 0
  local cur_rank = 1
  local parent, granp = 0, 0
  local l, r, k, v = self.l, self.r, self.key, self.value
  local w = self.w
  local lt = self.lt
  cur_idx = self.root
  while 0 < cur_idx do
    w[cur_idx] = w[cur_idx] + 1
    node_idxes_by_rank[cur_rank] = cur_idx
    cur_rank = cur_rank + 1
    if lt(key, k[cur_idx]) then
      cur_idx = l[cur_idx]
    else
      cur_idx = r[cur_idx]
    end
  end
  self.node_count = self.node_count + 1
  cur_idx = self.free_nodes[self.node_count]
  node_idxes_by_rank[cur_rank] = cur_idx
  w[cur_idx] = 1
  if cur_rank == 1 then
    self.root = cur_idx
  else
    parent = node_idxes_by_rank[cur_rank - 1]
    if lt(key, k[parent]) then
      l[parent] = cur_idx
    else
      r[parent] = cur_idx
    end
  end
  k[cur_idx], v[cur_idx], l[cur_idx], r[cur_idx] = key, value, 0, 0
  self:setRed(cur_idx)
  while true do
    cur_idx = node_idxes_by_rank[cur_rank]
    if cur_rank == 1 then
      self:setBlack(cur_idx)
      break
    end
    parent = node_idxes_by_rank[cur_rank - 1]
    if self:isRed(parent) then
      granp = node_idxes_by_rank[cur_rank - 2]
      if l[granp] == parent then
        if l[parent] == cur_idx then
          self:rotateR(granp, parent)
        else
          self:rotateLR(granp, parent, cur_idx)
        end
      else
        if l[parent] == cur_idx then
          self:rotateRL(granp, parent, cur_idx)
        else
          self:rotateL(granp, parent)
        end
      end
      self:setRed(granp)
      self:setBlack(parent)
      self:setBlack(cur_idx)
      cur_rank = cur_rank - 2
    else
      break
    end
  end
end

RBTree.remove = function(self, key)
  local l, r, k, v = self.l, self.r, self.key, self.value
  local w = self.w
  local lt = self.lt
  local node_idxes_by_rank = {}
  local cur_idx = 0
  local cur_rank = 1
  local parent, left, right, granc = 0, 0, 0, 0
  local resolve_state = 0 -- 0:OK, 1:left black count is small, 2:right is
  cur_idx = self.root
  while 0 < cur_idx do
    node_idxes_by_rank[cur_rank] = cur_idx
    if not lt(k[cur_idx], key) and not lt(key, k[cur_idx]) then
      break
    end
    cur_rank = cur_rank + 1
    if lt(key, k[cur_idx]) then
      cur_idx = l[cur_idx]
    else
      cur_idx = r[cur_idx]
    end
  end
  if 0 == cur_idx then
    return -- NOT FOUND
  end
  if 0 == l[cur_idx] then
    for i = 1, cur_rank do
      local z = node_idxes_by_rank[i]
      w[z] = w[z] - 1
    end
    self.free_nodes[self.node_count] = cur_idx
    self.node_count = self.node_count - 1
    if cur_rank == 1 then
      self.root = r[cur_idx]
      if 0 < self.root then
        self:setBlack(self.root)
      end
      return
    else
      parent = node_idxes_by_rank[cur_rank - 1]
      if l[parent] == cur_idx then
        l[parent] = r[cur_idx]
        if not self:isRed(cur_idx) then
          resolve_state = 1
        end
      else
        r[parent] = r[cur_idx]
        if not self:isRed(cur_idx) then
          resolve_state = 2
        end
      end
      cur_idx = parent
      cur_rank = cur_rank - 1
    end
  else
    local swap_idx = cur_idx
    cur_idx = l[cur_idx]
    cur_rank = cur_rank + 1
    node_idxes_by_rank[cur_rank] = cur_idx
    while 0 < r[cur_idx] do
      cur_idx = r[cur_idx]
      cur_rank = cur_rank + 1
      node_idxes_by_rank[cur_rank] = cur_idx
    end
    k[swap_idx], v[swap_idx] = k[cur_idx], v[cur_idx]
    for i = 1, cur_rank do
      local z = node_idxes_by_rank[i]
      w[z] = w[z] - 1
    end
    parent = node_idxes_by_rank[cur_rank - 1]
    if parent == swap_idx then
      l[parent] = l[cur_idx]
      if not self:isRed(cur_idx) then resolve_state = 1 end
    else
      r[parent] = l[cur_idx]
      if not self:isRed(cur_idx) then resolve_state = 2 end
    end
    self.free_nodes[self.node_count] = cur_idx
    self.node_count = self.node_count - 1
    cur_idx = parent
    cur_rank = cur_rank - 1
  end
  while 0 < resolve_state do
    if resolve_state == 1 then
      right = r[cur_idx]
      if self:isRed(right) then
        self:rotateL(cur_idx, right)
        cur_idx = right
        right = r[cur_idx]
        granc = l[right]
        if 0 < granc and self:isRed(granc) then
          self:rotateRL(cur_idx, right, granc)
          self:setBlack(granc)
          break
        end
        granc = r[right]
        if 0 < granc and self:isRed(granc) then
          self:rotateL(cur_idx, right)
          self:setBlack(granc)
          break
        end
        self:setBlack(cur_idx)
        self:setRed(right)
        break
      else
        granc = l[right]
        if 0 < granc and self:isRed(granc) then
          self:rotateRL(cur_idx, right, granc)
          self:setBlack(granc)
          break
        end
        granc = r[right]
        if 0 < granc and self:isRed(granc) then
          self:rotateL(cur_idx, right)
          self:setBlack(granc)
          break
        end
        self:setRed(right)
        if self:isRed(cur_idx) then
          self:setBlack(cur_idx)
          break
        end
        if cur_rank == 1 then break end
        cur_rank = cur_rank - 1
        parent = node_idxes_by_rank[cur_rank]
        if l[parent] == cur_idx then
          resolve_state = 1
        else
          resolve_state = 2
        end
        cur_idx = parent
      end
    else
      left = l[cur_idx]
      if self:isRed(left) then
        self:rotateR(cur_idx, left)
        cur_idx = left
        left = l[cur_idx]
        granc = r[left]
        if 0 < granc and self:isRed(granc) then
          self:rotateLR(cur_idx, left, granc)
          self:setBlack(granc)
          break
        end
        granc = l[left]
        if 0 < granc and self:isRed(granc) then
          self:rotateR(cur_idx, left)
          self:setBlack(granc)
          break
        end
        self:setBlack(cur_idx)
        self:setRed(left)
        break
      else
        granc = r[left]
        if 0 < granc and self:isRed(granc) then
          self:rotateLR(cur_idx, left, granc)
          self:setBlack(granc)
          break
        end
        granc = l[left]
        if 0 < granc and self:isRed(granc) then
          self:rotateR(cur_idx, left)
          self:setBlack(granc)
          break
        end
        self:setRed(left)
        if self:isRed(cur_idx) then
          self:setBlack(cur_idx)
          break
        end
        if cur_rank == 1 then break end
        cur_rank = cur_rank - 1
        parent = node_idxes_by_rank[cur_rank]
        if l[parent] == cur_idx then
          resolve_state = 1
        else
          resolve_state = 2
        end
        cur_idx = parent
      end
    end
  end
end

RBTree.getLeft = function(self, comp_key)
  local l, r, k, v = self.l, self.r, self.key, self.value
  local lt = self.lt
  local ret_key, ret_value = nil, nil
  local cur_idx = self.root
  while 0 < cur_idx do
    if not lt(comp_key, k[cur_idx]) then
      ret_key, ret_value = k[cur_idx], v[cur_idx]
      cur_idx = r[cur_idx]
    else
      cur_idx = l[cur_idx]
    end
  end
  return ret_key, ret_value
end

RBTree.getRight = function(self, comp_key)
  local l, r, k, v = self.l, self.r, self.key, self.value
  local lt = self.lt
  local ret_key, ret_value = nil, nil
  local cur_idx = self.root
  while 0 < cur_idx do
    if lt(k[cur_idx], comp_key) then
      cur_idx = r[cur_idx]
    else
      ret_key, ret_value = k[cur_idx], v[cur_idx]
      cur_idx = l[cur_idx]
    end
  end
  return ret_key, ret_value
end

RBTree.front = function(self)
  local l, k, v = self.l, self.key, self.value
  local ret_key, ret_value = nil, nil
  local cur_idx = self.root
  while 0 < cur_idx do
    ret_key, ret_value = k[cur_idx], v[cur_idx]
    cur_idx = l[cur_idx]
  end
  return ret_key, ret_value
end

RBTree.back = function(self)
  local r, k, v = self.r, self.key, self.value
  local ret_key, ret_value = nil, nil
  local cur_idx = self.root
  while 0 < cur_idx do
    ret_key, ret_value = k[cur_idx], v[cur_idx]
    cur_idx = r[cur_idx]
  end
  return ret_key, ret_value
end

RBTree.access = function(self, pos)
  local l, r, w = self.l, self.r, self.w
  local k, v = self.key, self.value
  if self.node_count < pos then return nil, nil end
  local cur_idx = self.root
  local ret_key, ret_value = k[cur_idx], v[cur_idx]
  while 0 < cur_idx do
    local li = l[cur_idx]
    local lw = li == 0 and 0 or w[li]
    if lw + 1 == pos then break end
    if pos <= lw then
      cur_idx = li
    elseif lw + 1 == pos then
      break
    else
      pos = pos - lw - 1
      cur_idx = r[cur_idx]
    end
    ret_key, ret_value = k[cur_idx], v[cur_idx]
  end
  return ret_key, ret_value
end

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

local n = io.read("*n")
local a = {}
for i = 1, n do
  a[i] = io.read("*n")
end
if n == 1 then
  print(a[1])
elseif n % 2 == 1 then
  print(1)
elseif n == 2 then
  local b = 1LL * a[1] * a[2]
  b = tostring(b):gsub("LL", "")
  print(b)
else
  local rb = RBTree.new(n)
  for i = 1, n do
    rb:push(a[i], true)
  end
  for i = 1, n - 1 do
    if i % 2 == 1 then
      local v1 = rb:front()
      rb:remove(v1)
      local v2 = rb:front()
      rb:remove(v2)
      v1 = v1 * v2
      if 1000000007 < v1 then v1 = 1000000007 end
      rb:push(v1, true)
    else
      local v1 = rb:back()
      rb:remove(v1)
      local v2 = rb:back()
      rb:remove(v2)
      rb:push(1, true)
    end
  end
  local ret = rb:front()
  print(ret)
end

yukicoder

結果

テストケース

ソースコード