Submission #6439754


Source Code Expand

S = input()
K = int(input())
L = len(S)

V = [[] for _ in range(26)]
for i, s in enumerate(S):
    V[ord(s) - ord('a')].append(i)

# dp = [{a: 0 for a in map(chr, range(ord('a'), ord('z')+1))} for _ in range(L+1)]
dp = [[0 for _ in range(26)] for _ in range(L+1)]
dp[1][ord(S[-1]) - ord('a')] = 1

cum = 0
for i in range(2,L+1):
    s = ord(S[-i]) - ord('a')
    dp[i][s] = 1
    # for abc in map(chr, range(ord('a'), ord('z')+1)):
    for abc in range(26):
        dp[i][abc] += dp[i-1][abc]
        # if dp[i-1].get(abc):
        if dp[i-1][abc]:
            dp[i][s] += dp[i-1][abc]
    dp[i][s] -= dp[i-1][s]
    cum += dp[i][s] - 1

ans = ''
if cum >= K:
    cnt = K
    pos = 0
    while cnt > 0 and pos < L:
        # for abc in map(chr, range(ord('a'), ord('z')+1)):
        for abc in range(26):
            if cnt - dp[-pos-1][abc] > 0:
                cnt -= dp[-pos-1][abc]
            else:
                ans += chr(abc + ord('a'))
                # pos = S.find(ans[-1], pos) + 1
                for v in V[abc]:
                    if v > pos:
                        pos = v + 1
                        break
                cnt -= 1
                break

print(ans or 'Eel')

Submission Info

Submission Time
Task G - 辞書順
User qython
Language PyPy3 (2.4.0)
Score 0
Code Size 1240 Byte
Status WA
Exec Time 2136 ms
Memory 539832 KB

Judge Result

Set Name All
Score / Max Score 0 / 4
Status
AC × 3
WA × 1
TLE × 1
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 TLE 2136 ms 539832 KB
01 WA 381 ms 67804 KB
02 AC 164 ms 38256 KB
90 AC 164 ms 38256 KB
91 AC 163 ms 38256 KB