結果
問題 | No.911 ラッキーソート |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
local bls, brs = bit.lshift, bit.rshiftlocal mfl, mce = math.floor, math.ceillocal band = bit.bandlocal function lltonumber(str)local ret = 0LLfor i = 1, #str doret = ret * 10LL + str:sub(i, i):byte() - 48endreturn retendlocal 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 dot[i] = 3endlocal astr_all = io.read()local allbits = {}for astr in astr_all:gmatch("%d+") doallbits[#allbits + 1] = {}local i = #allbitsif #astr < 11 thenlocal a = tonumber(astr)for j = 1, countlim doallbits[i][j] = a % 2a = brs(a, 1)endelselocal top = astr:sub(1, 9)top = tonumber(top)local bottom = astr:sub(10, #astr)bottom = tonumber(bottom)for j = 1, countlim doallbits[i][j] = bottom % 2if top % 2 == 1 thentop = brs(top, 1)bottom = bottom + (10^(#astr - 9))bottom = mfl(bottom / 2)elsetop = brs(top, 1)bottom = mfl(bottom / 2)endendend-- 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-- endendlocal valid = truelocal t1, t2, t3 = {countlim}, {1}, {n}while 0 < #t1 dolocal pos, left, right = t1[#t1], t2[#t2], t3[#t3]table.remove(t1) table.remove(t2) table.remove(t3)if left == right thenif 1 < pos thentable.insert(t1, pos - 1) table.insert(t2, left) table.insert(t3, right)endelselocal lval = allbits[left][pos]local rval = allbits[right][pos]if lval == rval thenfor i = left + 1, right - 1 doif allbits[i][pos] ~= lval thenvalid = false breakendendif not valid then break endif 1 < pos thentable.insert(t1, pos - 1) table.insert(t2, left) table.insert(t3, right)endelselocal turnpos = nilfor i = left + 1, right doif allbits[i][pos] ~= allbits[i - 1][pos] thenif turnpos then valid = false breakelseturnpos = iendendendif not valid then break endif lval == 0 thent[pos] = band(t[pos], 1)elset[pos] = band(t[pos], 2)endif t[pos] == 0 then valid = false break endif pos ~= 1 thentable.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)endendendend-- print(valid)-- print(table.concat(t, " "))local function getCount(max)local maxbits = {}for i = 1, countlim domaxbits[i] = max % 2LL == 1LL and 1 or 0max = max / 2LLendlocal dpmax, dpnormal = {}, {}for i = 1, countlim dodpmax[i] = 0dpnormal[i] = 0enddpmax[countlim] = 1LLdpnormal[countlim] = 0LLfor i = countlim - 1, 1, -1 doif t[i] == 3 thendpmax[i] = dpmax[i + 1]dpnormal[i] = dpnormal[i + 1] * 2LLif maxbits[i] == 1 thendpnormal[i] = dpnormal[i] + dpmax[i + 1]endelseif t[i] == 2 then-- only "1" is availableif maxbits[i] == 0 thendpmax[i] = 0elsedpmax[i] = dpmax[i + 1]enddpnormal[i] = dpnormal[i + 1]else -- t[i] == 1-- only "0" is availableif maxbits[i] == 0 thendpmax[i] = dpmax[i + 1]dpnormal[i] = dpnormal[i + 1]elsedpmax[i] = 0dpnormal[i] = dpnormal[i + 1] + dpmax[i + 1]endendendreturn dpnormal[1] + dpmax[1]endif valid thenlocal cnt = getCount(r)if 0 < l thencnt = cnt - getCount(l - 1)endlocal str = tostring(cnt):gsub("LL", "")print(str)elseprint(0)end