結果
問題 | No.130 XOR Minimax |
ユーザー |
👑 |
提出日時 | 2020-04-23 21:36:22 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 6,816 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-01 17:53:39 |
合計ジャッジ時間 | 2,465 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
local bls, brs = bit.lshift, bit.rshift local mfl = math.floor local mmi, mma = math.min, math.max local function comp(a, b) return a < b end local function lower_bound(ary, min, max, x) if not comp(ary[min], x) then return min end if comp(ary[max], x) then return max + 1 end while 1 < max - min do local mid = mfl((min + max) / 2) if comp(ary[mid], x) then min = mid else max = mid end end return max end local n = io.read("*n") local a = {} for i = 1, n do a[i] = io.read("*n") end table.sort(a) local ret = 1000000007 local function rec(l, r, stage, score, mask) for i = stage, 0, -1 do local lb = lower_bound(a, l, r, mask + bls(1, i)) if lb <= l then mask = mask + bls(1, i) elseif r < lb then else rec(l, lb - 1, i - 1, score + bls(1, i), mask) rec(lb, r, i - 1, score + bls(1, i), mask + bls(1, i)) return end end ret = mmi(ret, score) end rec(1, n, 29, 0, 0) print(ret)