結果

問題 No.3244 Range Multiple of 8 Query
ユーザー kidodesu
提出日時 2025-08-22 23:49:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,243 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 849,032 KB
最終ジャッジ日時 2025-08-22 23:50:36
合計ジャッジ時間 6,637 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, q = map(int, input().split())
S = input()
S = [int(S[i])%8 for i in range(n)]

C = set()
inf = 1 << 60
D = [inf] * 1000
from itertools import permutations as P
for now in range(1000):
    if now % 8:
        continue
    a = now
    now = str(now)
    now = "0" * (3 - len(now)) + now
    if "8" in now or "9" in now:
        continue
    D[a] = 0
    for per in P(range(3), 3):
        nxt = ""
        for i in range(3):
            nxt += now[per[i]]
        nxt = int(nxt)
        if per == (1, 0, 2) or per == (0, 2, 1):
            D[nxt] = min(D[nxt], 1)
        elif per == (2, 1, 0):
            D[nxt] = min(D[nxt], 3)
        else:
            D[nxt] = min(D[nxt], 2)
    C.add("".join(sorted(now)))

def cal(A, r):
    idx0, idx1, idx2 = sorted(A)
    if idx0 == -1:
        return -1, inf
    nxt = S[idx0] * 100 + S[idx1] * 10 + S[idx2]
    return idx0, D[nxt] + (r-idx2-1)*3 + (idx2-idx1-1)*2 + (idx1-idx0-1)
C = list(C)
K = [set() for _ in range(8)]
for c in C:
    for i in range(3):
        K[int(c[i])].add(c)
for i in range(8):
    K[i] = list(K[i])
N = len(C)
I = {C[i]: i for i in range(N)}
E = [[-1, -1, -1] for _ in range(N)] 
dp = [[[-1, inf] for _ in range(N)] * N for _ in range(n+1)]
tt = 0
for i in range(n):
    tt -= 3
    for j in range(N):
        dp[i+1][j] = dp[i][j][:]
    if i == n:
        break
    a = S[i]
    for now in K[a]:
        idx = I[now]
        mi = -1
        ma = 2*n
        for j in range(3):
            if int(now[j]) == a and ma > E[idx][j]:
                mi = j
                ma = E[idx][j]
        E[idx][mi] = i
        ll, rep = cal(E[idx], i+1)
        dp[i+1][idx] = [ll, rep+tt]

for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    ans = inf
    if r - l == 1:
        if S[l] == 0:
            print(0)
        else:
            print(-1)
    elif r - l == 2:
        if not (S[l] * 10 + S[r-1]) % 8:
            print(0)
        elif not (S[r-1] * 10 + S[l]) % 8:
            print(1)
        else:
            print(-1)
    else:
        for i in range(N):
            if l <= dp[r][i][0]:
                ans = min(ans, dp[r][i][1]+r*3)
        if ans >= inf:
            print(-1)
        else:
            print(ans)
0