CSES - DatatÃ¤hti 2022 alku - Results
 Task: Ositus (Partitioning) Sender: Totska Submission time: 2021-10-17 20:00:20 Language: PyPy3 Status: READY Result: 100
Feedback
groupverdictscore
#1ACCEPTED40
#2ACCEPTED25
#3ACCEPTED35
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1, 2, 3details
#2ACCEPTED0.06 s1, 2, 3details
#3ACCEPTED0.06 s1, 2, 3details
#4ACCEPTED0.06 s1, 2, 3details
#5ACCEPTED0.06 s2, 3details
#6ACCEPTED0.08 s3details
#7ACCEPTED0.44 s3details

### Code

```from collections import deque
from string import ascii_lowercase
import cProfile
#

s = "-" + input() + "x"

# s = ["-", read(0, 999999999).decode().strip(), "x"]
# s = ["-", input(), "x"]
# def opt_join(x):
#     global s
#     s = ''.join(x)
#
# opt_join(s)

# print(s)

end = len(s) - 1
maxnb = [end+1 for _ in range(end+1)]
maxnb.append(-1)

minimum = end + 1

seen = {ascii_lowercase[i]: end+1 for i in range(26)}

last = {i: -1 for i in range(end+2)}
distances = deque()

prevdist = 9999999

for i in range(end, 0, -1):
minimum = min(minimum, seen[s[i]])

if minimum < prevdist:
distances.insert(0, minimum)
prevdist = minimum

# maxnb[i] = seen[s[i]]
maxnb[i] = minimum
seen[s[i]] = i

last[maxnb[i]] = max(last[maxnb[i]], i)

seen.clear()

def getsum(a, b):
return sumtable[b] - sumtable[a-1]

# i+1 indeksointi
sumtable = [0, 1]

MOD = 10**9 + 7

start = 1
mindist = distances.popleft()
for i in range(2, end+1):
# check
if i > mindist:
start = last[mindist] + 1
mindist = distances.popleft()

sumtable.append((sumtable[i-1] % MOD + getsum(start, i-1) % MOD) % MOD)

print((getsum(end, end)) % MOD)
# print(int(getval(end, -1) % MOD))

# pr.disable()
# pr.print_stats(sort='time')```

### Test details

#### Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
a

correct output
1

user output
1

#### Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
abcdefghij

correct output
512

user output
512

#### Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
abcabaacbc

correct output
120

user output
120

#### Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
aaxxxxxxaa

correct output
4

user output
4

#### Test 5

Group: 2, 3

Verdict: ACCEPTED

input
mfyzvoxmppoxcvktmcjkryyocfweub...

correct output
643221148

user output
643221148

#### Test 6

Group: 3

Verdict: ACCEPTED

input
weinscqmmpgbrlboocvtbptgbahmwv...

correct output
831644159

user output
831644159

#### Test 7

Group: 3

Verdict: ACCEPTED

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...

correct output
816016015

user output
816016015