Contest Duration: - (local time) (150 minutes) Back to Home

Submission #17508898

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

INF = 1 << 60
sigma = 26
atcoder = np.array(list(b'atcoder'), np.int64) - ord('a')

@njit((i8[:], ), cache=True)
def precompute(S):
first_idx = np.full(sigma, INF, np.int64)
for i in range(len(S)):
s = S[i]
if first_idx[s] == INF:
first_idx[s] = i
return first_idx

@njit((i8[:], ), cache=True)
def inv(use_idx):
N = len(use_idx)
x = use_idx.sum()
for i in range(N):
for j in range(i):
if use_idx[j] < use_idx[i]:
x -= 1
return x

@njit((i8[:], i8[:], i8[:], i8), cache=True)
def solve(S, first_idx, atcoder, n):
# n 文字一致して、n+1 文字で大きいものをとる
if len(S) <= n:
return INF
use_idx = np.full(n + 1, INF, np.int64)
for i in range(n):
s = atcoder[i]
use_idx[i] = first_idx[s]
if use_idx[i] == INF:
return INF

target = -1 if n == len(atcoder) else atcoder[n]
idx = INF
for i in range(len(S)):
if S[i] <= target:
continue
ok = True
for j in use_idx[:n]:
if i == use_idx[j]:
ok = False
break
if ok:
idx = i
break
if idx == INF:
return INF
use_idx[n] = idx
return inv(use_idx)

def main():
for _ in range(T):
S = np.array(list(readline().rstrip()), np.int64) - ord('a')
ans = INF
for n in range(len(atcoder) + 1):
first_idx = precompute(S)
ans = min(ans, solve(S, first_idx, atcoder, n))
if ans >= INF:
ans = -1
print(ans)

main()```

#### Submission Info

Submission Time 2020-10-18 21:34:58+0900 A - atcoder < S maspy Python (3.8.2) 300 1917 Byte AC 508 ms 106512 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
 AC × 1
 AC × 2
Set Name Test Cases
Sample 00-sample-001.txt
All 00-sample-001.txt, 01-001.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 508 ms 105800 KB
01-001.txt AC 501 ms 106512 KB