結果
| 問題 | No.1859 ><<< |
| ユーザー |
👑  obakyan
|
| 提出日時 | 2022-03-20 00:54:47 |
| 言語 | Lua (LuaJit 2.1.1696795921) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,252 bytes |
| コンパイル時間 | 115 ms |
| コンパイル使用メモリ | 5,120 KB |
| 実行使用メモリ | 132,164 KB |
| 最終ジャッジ日時 | 2024-04-15 15:17:30 |
| 合計ジャッジ時間 | 23,682 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,624 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 1,893 ms
130,176 KB |
| testcase_05 | AC | 1,879 ms
130,304 KB |
| testcase_06 | AC | 1,824 ms
130,224 KB |
| testcase_07 | AC | 1,918 ms
130,088 KB |
| testcase_08 | AC | 1,860 ms
132,164 KB |
| testcase_09 | AC | 1,843 ms
130,176 KB |
| testcase_10 | AC | 442 ms
19,712 KB |
| testcase_11 | TLE | - |
| testcase_12 | AC | 1,951 ms
63,508 KB |
| testcase_13 | AC | 1,098 ms
33,344 KB |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
ソースコード
local mmi, mma = math.min, math.max
local mfl, mce = math.floor, math.ceil
local TSufA = {}
TSufA.makeSufA = function(self)
self.sufa = {}
local n = #self.str
local idx, tbl1, tbl2 = self.sufa, {}, {}
local tmp_tbl = {}
for i = 1, n do
idx[i] = i
tbl1[i] = self.str[i]
-- tbl1[i] = self.str:sub(i, i):byte() - 95 -- "a" = 97
tbl2[i] = 0
tmp_tbl[i] = 0
end
idx[n + 1], tbl1[n + 1], tbl2[n + 1] = n + 1, 1, 0
n = n + 1 -- add empty to last
table.sort(idx, function(a, b) return tbl1[a] < tbl1[b] end)
local step, stepflag = 1, true
while step < n do
local v = stepflag and tbl1 or tbl2
local vd = stepflag and tbl2 or tbl1
stepflag = not stepflag
local stepdst = {}
for i = 1, n do
local dst = i + step
if n < dst then dst = dst - n end
stepdst[i] = dst
end
local left, major = 1, v[idx[1]]
local minor_min = v[stepdst[idx[1]]]
local minor_max = minor_min
local minormap = {}
local cur = 0
for i = 1, n do
local minor = v[stepdst[idx[i]]]
if minormap[minor] then minormap[minor] = minormap[minor] + 1
else minormap[minor] = 1
end
minor_min, minor_max = mmi(minor_min, minor), mma(minor_max, minor)
local isend = i == n or major ~= v[idx[i + 1]]
if isend then
local right = i
if left == right then
cur = cur + 1
vd[idx[left]] = cur
elseif minor_min ~= minor_max then
local minortbl = {}
for k, _u in pairs(minormap) do table.insert(minortbl, k) end
table.sort(minortbl)
local offset = 0
for i = 1, #minortbl do
local cnt = minormap[minortbl[i]]
minormap[minortbl[i]] = i
minortbl[i] = offset -- reuse
offset = offset + cnt
end
for j = left, right do
local idxj = idx[j]
local minor_idx = minormap[v[stepdst[idxj]]]
local ofst = minortbl[minor_idx]
ofst = ofst + 1
minortbl[minor_idx] = ofst
tmp_tbl[ofst] = idxj
vd[idxj] = cur + minor_idx
end
cur = cur + #minortbl
for j = left, right do
idx[j] = tmp_tbl[j - left + 1]
end
else
cur = cur + 1
for j = left, right do
vd[idx[j]] = cur
end
end
if i < n then
left, major = i + 1, v[idx[i + 1]]
minor_min = v[stepdst[idx[i + 1]]]
minor_max = minor_min
minormap = {}
end
end
end
step = step * 2
end
-- remove empty from first (O(N))
table.remove(self.sufa, 1)
n = n - 1
self.sufa_inv = {}
for i = 1, n do self.sufa_inv[i] = 0 end
for i = 1, n do
self.sufa_inv[self.sufa[i]] = i
end
end
TSufA.makeLCPA = function(self)
assert(self.sufa)
local n = #self.sufa
self.lcpa = {}
local str, sufa, lcpa = self.str, self.sufa, self.lcpa
for i = 1, n - 1 do lcpa[i] = 0 end
local spos = 0
for i = 1, n do
local lcppos = self.sufa_inv[i]
if lcppos < n then
local len = spos
local p1, p2 = sufa[lcppos], sufa[lcppos + 1]
p1, p2 = p1 + spos, p2 + spos
while p1 <= n and p2 <= n do
if str[p1] == str[p2] then
len = len + 1
p1, p2 = p1 + 1, p2 + 1
else break
end
end
lcpa[lcppos] = len
spos = mma(0, len - 1)
end
end
end
local function tblcomp(a, b, bspos)
-- return a <= b:sub(bspos, #b)
local lim = mmi(#a, #b - bspos + 1)
for i = 1, lim do
if a[i] ~= b[bspos + i - 1] then
return a[i] < b[bspos + i - 1] and true or false
end
end
return #a <= #b - bspos + 1
end
TSufA.lowerBound = function(self, s)
if tblcomp(s, self.str, self.sufa[1]) then
return 1
end
if not tblcomp(s, self.str, self.sufa[#self.str]) then
return #self.str + 1
end
local min, max = 1, #self.str
while 1 < max - min do
local mid = mfl((min + max) / 2)
if tblcomp(s, self.str, self.sufa[mid]) then
max = mid
else
min = mid
end
end
return max
end
TSufA.create = function(self, str)
self.str = str
self:makeSufA()
self:makeLCPA()
end
TSufA.new = function(str)
local obj = {}
setmetatable(obj, {__index = TSufA})
obj:create(str)
return obj
end
local n = io.read("*n")
local a = {}
for i = 1, n do
a[i] = io.read("*n")
end
io.read()
local t = {}
for i = 1, n - 1 do
if a[i] < a[i + 1] then
t[i] = 3
else
t[i] = 2
end
end
if a[n] < a[1] then
t[n] = 3
else
t[n] = 2
end
for i = 1, n - 2 do
t[n + i] = t[i]
end
-- t = table.concat(t)
local sa = TSufA.new(t)
-- print(os.clock())
local s = io.read()
local z = {}
for i = 1, n - 1 do
z[i] = s:sub(i, i) == "<" and 3 or 2
end
local lb = sa:lowerBound(z)
-- print(lb, table.concat(sa.sufa, " "), t)
if #t < lb then
print(-1)
os.exit()
end
local pos = sa.sufa[lb]
if n < pos then print(-1) os.exit() end
for i = 1, n - 1 do
if z[i] ~= t[pos + i - 1] then
print(-1) os.exit()
end
end
local cand = pos
while true do
if lb <= 2 * n - 4 and n - 1 <= sa.lcpa[lb] then
lb = lb + 1
cand = mmi(cand, sa.sufa[lb])
else
break
end
end
print(cand - 1)
-- print(os.clock())