結果
問題 | No.1651 Removing Cards |
ユーザー |
👑 |
提出日時 | 2024-11-07 21:31:11 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 1,958 ms / 2,000 ms |
コード長 | 2,543 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 5,248 KB |
実行使用メモリ | 53,680 KB |
最終ジャッジ日時 | 2024-11-07 21:31:47 |
合計ジャッジ時間 | 32,383 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
local pow2 = {1}for i = 2, 28 do pow2[i] = pow2[i - 1] * 2 endlocal function mergesort(ary, buf, sortfunc)local n = #arylocal rep, mul = 0, 1while mul < n dorep, mul = rep + 1, mul * 2endfor irep = 1, rep dolocal src = irep % 2 == 1 and ary or buflocal dst = irep % 2 == 1 and buf or arylocal sz = pow2[irep]local boxcnt = pow2[rep - irep + 1]for i = 1, boxcnt dolocal il = 1 + sz * 2 * (i - 1)local ir = il + szlocal llim = ir - 1local rlim = llim + szlocal id = illocal rem = sz * 2if n <= llim thenfor k = il, n do dst[k] = src[k] endbreakelseif n <= rlim thenrlim = nrem = n - il + 1endfor j = 1, rem doif sortfunc(src[ir], src[il]) thendst[id] = src[ir] ir = ir + 1elsedst[id] = src[il] il = il + 1endid = id + 1if llim < il thenfor k = 0, rem - j - 1 do dst[id + k] = src[ir + k] endbreakelseif rlim < ir thenfor k = 0, rem - j - 1 do dst[id + k] = src[il + k] endbreakendendendend-- local sorted_tbl_is_written_in_ary1 = rep % 2 == 0return rep % 2 == 0endlocal ffi = require("ffi")local C = ffi.Cffi.cdef[[long long atoll(const char*);]]local function lltonumber(str)return C.atoll(str)endlocal k, q = io.read("*n", "*n", "*l")k = 1LL * klocal lim = 1000000007LL * 1000000007LLlocal function solve(x)local min, max = x - 1LL, x * 2LL + 10while 1LL < max - min dolocal mid = (min + max) / 2LLlocal v = (mid + k - 1LL) / kif x + 1LL <= mid - v thenmax = midelsemin = midendendreturn max - 1LLendlocal t = {}local sz = 1LLwhile sz < lim dosz = solve(sz)table.insert(t, sz)end-- print(t[1])-- print(#t, t[#t])-- os.exit()local a = {}local aidx = {}local ans = {}for iq = 1, q doaidx[iq] = iqlocal z = io.read()z = string.rep("0", 19 - #z) .. za[iq] = zans[iq] = 0endlocal buf = {}local f = mergesort(aidx, buf, function(x, y) return a[x] < a[y] end)if not f then aidx = buf endlocal tpos = 1for iq = 1, q dolocal i = aidx[iq]local n = lltonumber(a[i])if n == 1LL thenans[i] = 1elsewhile tpos <= #t and t[tpos] < n dotpos = tpos + 1endif tpos == 1 thenans[i] = 2elseans[i] = tostring(t[tpos - 1] + 1LL):gsub("LL", "")endendendprint(table.concat(ans, "\n"))