Submission #17508898


Source Code Expand

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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():
    T = int(readline())
    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
Task A - atcoder < S
User maspy
Language Python (3.8.2)
Score 300
Code Size 1917 Byte
Status AC
Exec Time 508 ms
Memory 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