제출 #1167308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167308		kittikati	JJOOII 2 (JOI20_ho_t2)	Pypy 3	100 / 100	246 ms	92824 KiB

ho_t2

def bsearch(l, inp):
    p1 = 0
    p2 = len(l)-1
    while p1 != p2:
        avg = (p1+p2)//2
        curnt = l[avg][0]
        if curnt > inp:
            p2 = avg
        elif curnt < inp:
            p1 = avg + 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))

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'ho_t2.py'...

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

=======

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