oj.uz

Submission #48761

# Submission time Handle Problem Language Result Execution time Memory
48761 2018-05-18T16:26:59 Z leejseo 구간 성분 (KOI15_interval) PyPy
30 / 100
 686 ms 131072 KB 
from bisect import bisect_left as bl
from bisect import bisect_right as br
A = raw_input()
B = raw_input()
N = len(A)
M = len(B)
va = [ ord(i) - 96 for i in A ]
vb = [ ord(i) - 96 for i in B ]
hchar = [98213451]
for i in xrange(1, 27):
    hchar.append((hchar[-1] * hchar[0])%1000000009)
A = None
B = None
sa = [0]*(N+1)
sb = [0]*(M+1)
cha = [ [0]*(N+1) for i in xrange(27) ]
chb = [ [0]*(M+1) for i in xrange(27) ]
for i in xrange(N):
    sa[i+1] = sa[i] + hchar[va[i]]
    for c in xrange(1, 27): cha[c][i+1] = cha[c][i]
    cha[va[i]][i+1] += 1
for i in xrange(M):
    sb[i+1] = sb[i] + hchar[vb[i]]
    for c in xrange(1, 27): chb[c][i+1] = chb[c][i]
    chb[vb[i]][i+1] = chb[vb[i]][i] + 1
inb   = []
inb_v = []
for k in xrange(M):
    for i in xrange(M-k):
        inb.append((sb[i+k+1] - sb[i], k, i))
        inb_v.append(sb[i+k+1] - sb[i])
inb.sort();inb_v.sort()
ans = 0
for k in xrange(N):
    for i in xrange(N-k):
        if k+1 == ans : break
        val = sa[i+k+1] - sa[i]
        st, ed = bl(inb_v, val), br(inb_v, val)
        for j in xrange(st, ed):
            if k+1 == ans: break
            nv, nk, ni = inb[j]
            if k != nk: continue
            b = True
            for c in xrange(1, 27):
                if cha[c][i+k+1] - cha[c][i] != chb[c][ni+nk+1] - chb[c][ni] : b = False; break
            if b : ans = max(ans, k+1)
print ans

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11496 KB Output is correct
2 Correct 75 ms 15180 KB Output is correct
3 Correct 95 ms 16224 KB Output is correct
4 Correct 118 ms 18516 KB Output is correct
5 Correct 129 ms 18724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 39864 KB Output is correct
2 Correct 388 ms 39864 KB Output is correct
3 Correct 342 ms 39864 KB Output is correct
4 Correct 156 ms 39932 KB Output is correct
5 Correct 568 ms 39932 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 226 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -