結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
|
提出日時 | 2025-08-22 23:03:56 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,262 bytes |
コンパイル時間 | 392 ms |
コンパイル使用メモリ | 82,852 KB |
実行使用メモリ | 137,896 KB |
最終ジャッジ日時 | 2025-08-22 23:04:29 |
合計ジャッジ時間 | 23,277 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 16 TLE * 1 -- * 16 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### inf = float("inf") # 2桁以下は愚直 # 末尾の3桁を125通り試す # n, q = na() s = [int(i) for i in input()] F = [[] for i in range(n + 1)] que = [] for i in range(q): l, r = na() l -= 1 que.append((l, r)) if r - l >= 3: F[r].append(i) D = [] for i in range(104, 1000, 8): x = str(i) if "0" in x or len(x) != 3: continue D.append([int(x[0]), int(x[1]), int(x[2])]) # print(D) lis = [[-inf, -inf, -inf] for i in range(10)] ans = [inf] * q def inv(x): ans = 0 for i in range(3): for j in range(i+1, 3): if x[i] < x[j]: ans += 1 return ans for r in range(1, n + 1): lis[s[r-1]] = [lis[s[r-1]][1], lis[s[r-1]][2], r-1] # print(r, lis[9]) for i in F[r]: l = que[i][0] for x in D: # if x[0] == x[1] == x[2]: # if lis[x[0]][0] >= l: # ans[i] = min(ans[i], (r-1 + r-2 + r-3)-sum(lis[x[0]])) # elif A = [2] * 10 ff = [] flag = 1 for j in range(2, -1, -1): if lis[x[j]][A[x[j]]] >= l: ff.append(lis[x[j]][A[x[j]]]) A[x[j]] -= 1 else: flag = 0 if flag: # print(l, r, x, ff) ans[i] = min(ans[i], (r-1 + r-2 + r-3) - sum(ff) + inv(ff)) else: # print(l, r, x, ff, "!") pass for i in range(q): l, r = que[i] if r - l == 1: if s[l] == 8: print(0) else: print(-1) elif r - l == 2: if s[l] * 10 + s[l+1] == 0: print(0) elif s[l+1] * 10 + s[l] == 0: print(1) else: print(-1) else: if ans[i] == inf: print(-1) else: print(ans[i])