#466582 (Lua) No.911 ラッキーソート

• 問題: No.911 ラッキーソート
• ユーザー: 👑 obakyan
• 提出日時: 2020-04-18 17:26:07
• 言語: Lua (LuaJit 2.1.1734355927)
• 結果: AC
• 実行時間: 1,597 ms / 2,000 ms
• コード長: 3,922 bytes
• コンパイル時間: 167 ms
• コンパイル使用メモリ: 6,944 KB
• 実行使用メモリ: 146,236 KB
• 最終ジャッジ日時: 2024-10-04 00:00:30
• 合計ジャッジ時間: 29,333 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 46

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
local bls, brs = bit.lshift, bit.rshift
local mfl, mce = math.floor, math.ceil
local band = bit.band
local function lltonumber(str)
  local ret = 0LL
  for i = 1, #str do
    ret = ret * 10LL + str:sub(i, i):byte() - 48
  end
  return ret
end
local n, l, r = io.read():match("(%d+) (%d+) (%d+)")
n = tonumber(n)
l = lltonumber(l)
r = lltonumber(r)
local t = {}
local countlim = 64
-- 1 or 3: can use "0", 2 or 3: can use "1"
for i = 1, countlim do
  t[i] = 3
end
local astr_all = io.read()
local allbits = {}
for astr in astr_all:gmatch("%d+") do
  allbits[#allbits + 1] = {}
  local i = #allbits
  if #astr < 11 then
    local a = tonumber(astr)
    for j = 1, countlim do
      allbits[i][j] = a % 2
      a = brs(a, 1)
    end
  else
    local top = astr:sub(1, 9)
    top = tonumber(top)
    local bottom = astr:sub(10, #astr)
    bottom = tonumber(bottom)
    for j = 1, countlim do
      allbits[i][j] = bottom % 2
      if top % 2 == 1 then
        top = brs(top, 1)
        bottom = bottom + (10^(#astr - 9))
        bottom = mfl(bottom / 2)
      else
        top = brs(top, 1)
        bottom = mfl(bottom / 2)
      end
    end
  end
  -- local a = lltonumber(astr)
  -- allbits[#allbits + 1] = {}
  -- local i = #allbits
  -- for j = 1, countlim do
  --   allbits[i][j] = a % 2LL == 1LL and 1 or 0
  --   a = a / 2LL
  -- end
end
local valid = true
local t1, t2, t3 = {countlim}, {1}, {n}
while 0 < #t1 do
  local pos, left, right = t1[#t1], t2[#t2], t3[#t3]
  table.remove(t1) table.remove(t2) table.remove(t3)
  if left == right then
    if 1 < pos then
      table.insert(t1, pos - 1) table.insert(t2, left) table.insert(t3, right)
    end
  else
    local lval = allbits[left][pos]
    local rval = allbits[right][pos]
    if lval == rval then
      for i = left + 1, right - 1 do
        if allbits[i][pos] ~= lval then
          valid = false break
        end
      end
      if not valid then break end
      if 1 < pos then
        table.insert(t1, pos - 1) table.insert(t2, left) table.insert(t3, right)
      end
    else
      local turnpos = nil
      for i = left + 1, right do
        if allbits[i][pos] ~= allbits[i - 1][pos] then
          if turnpos then valid = false break
          else
            turnpos = i
          end
        end
      end
      if not valid then break end
      if lval == 0 then
        t[pos] = band(t[pos], 1)
      else
        t[pos] = band(t[pos], 2)
      end
      if t[pos] == 0 then valid = false break end
      if pos ~= 1 then
        table.insert(t1, pos - 1) table.insert(t2, left) table.insert(t3, turnpos - 1)
        table.insert(t1, pos - 1) table.insert(t2, turnpos) table.insert(t3, right)
      end
    end
  end
end
-- print(valid)
-- print(table.concat(t, " "))
local function getCount(max)
  local maxbits = {}
  for i = 1, countlim do
    maxbits[i] = max % 2LL == 1LL and 1 or 0
    max = max / 2LL
  end
  local dpmax, dpnormal = {}, {}
  for i = 1, countlim do
    dpmax[i] = 0
    dpnormal[i] = 0
  end
  dpmax[countlim] = 1LL
  dpnormal[countlim] = 0LL
  for i = countlim - 1, 1, -1 do
    if t[i] == 3 then
      dpmax[i] = dpmax[i + 1]
      dpnormal[i] = dpnormal[i + 1] * 2LL
      if maxbits[i] == 1 then
        dpnormal[i] = dpnormal[i] + dpmax[i + 1]
      end
    elseif t[i] == 2 then
      -- only "1" is available
      if maxbits[i] == 0 then
        dpmax[i] = 0
      else
        dpmax[i] = dpmax[i + 1]
      end
      dpnormal[i] = dpnormal[i + 1]
    else -- t[i] == 1
      -- only "0" is available
      if maxbits[i] == 0 then
        dpmax[i] = dpmax[i + 1]
        dpnormal[i] = dpnormal[i + 1]
      else
        dpmax[i] = 0
        dpnormal[i] = dpnormal[i + 1] + dpmax[i + 1]
      end
    end
  end
  return dpnormal[1] + dpmax[1]
end
if valid then
  local cnt = getCount(r)
  if 0 < l then
    cnt = cnt - getCount(l - 1)
  end
  local str = tostring(cnt):gsub("LL", "")
  print(str)
else
  print(0)
end
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX