Submission #1167306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167306		kittikati	JJOOII 2 (JOI20_ho_t2)	Pypy 3	0 / 100	132 ms	48792 KiB

ho_t2

def bsearch(l, inp):
    p1 = 0
    p2 = len(l)-1
    a = 0
    #print("b")
    while p1 != p2 and a < 10:
        avg = (p1+p2)//2
        curnt = l[avg][0]
        if curnt > inp:
            p2 = avg - 1
        elif curnt < inp:
            p1 = avg + 1
        a += 1
    avg = (p1+p2)//2
    curnt = l[avg][0]
    #print(curnt)
    if curnt >= inp:
        return avg
    else:
        return -1
            
N, K = [int(i) for i in input().split()]
S = input()
results = set([])
Jpos=[]
Opos=[]
Ipos=[]
J1=[]
O1=[]
I1=[]
for i in range(N):
    if S[i] == "J":
        Jpos.append(i)
    if S[i] == "O":
        Opos.append(i)
    if S[i] == "I":
        Ipos.append(i)
for i in range(len(Jpos)-K+1):
    J1.append([Jpos[i], Jpos[i+K-1]])
for i in range(len(Opos)-K+1):
    O1.append([Opos[i], Opos[i+K-1]])
for i in range(len(Ipos)-K+1):
    I1.append([Ipos[i], Ipos[i+K-1]])
#print(J1)
#print(O1)
#print(I1)
for x in J1:
    s1 = bsearch(O1, x[1])
    if s1 != -1:
        s2 = bsearch(I1, O1[s1][1])
        if s2 != -1:
            results.add(I1[s2][1]-x[0]-K*3+1)
if results == set([]):
    print(-1)
else:
    print(min(results))

Compilation message (stdout)

Compiling 'ho_t2.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87