結果

問題 No.3244 Range Multiple of 8 Query
ユーザー kidodesu
提出日時 2025-08-22 23:55:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,520 ms / 5,000 ms
コード長 2,322 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 126,508 KB
最終ジャッジ日時 2025-08-22 23:56:46
合計ジャッジ時間 48,181 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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)

def judge(l, r):
    l -= 1
    ans = inf
    if r - l == 1:
        if S[l] == 0:
            return 0
        else:
            return -1
    elif r - l == 2:
        if not (S[l] * 10 + S[r-1]) % 8:
            return 0
        elif not (S[r-1] * 10 + S[l]) % 8:
            return 1
        else:
            return -1
    else:
        for i in range(N):
            if l <= dp[i][0]:
                ans = min(ans, dp[i][1]+r*3)
        if ans >= inf:
            return -1
        else:
            return ans

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)]
tt = 0

LR = [list(map(int, input().split())) + [_] for _ in range(q)]
LR.sort(key = lambda x: x[1])
Ans = [-1] * q
tmp = 0

for i in range(n):
    tt -= 3
    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[idx] = [ll, rep+tt]
    while tmp < q and LR[tmp][1] == i + 1:
        Ans[LR[tmp][2]] = judge(LR[tmp][0], LR[tmp][1])
        tmp += 1

for ans in Ans:
    print(ans)
0