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 |
|
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 |