Problem:


Score : 500 points

Problem Statement

Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.

You are given an integer C and a string S. Takahashi will choose his workdays as follows:

After working for a day, he will refrain from working on the subsequent C days.

If the i-th character of S is x, he will not work on Day i, where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.

Find all days on which Takahashi is bound to work.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq N

0 \leq C \leq N

The length of S is N.

Each character of S is o or x.

Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.

Input

Input is given from Standard Input in the following format:

N K C
S

Output

Print all days on which Takahashi is bound to work in ascending order, one per line.

Sample Input 1

11 3 2
ooxxxoxxxoo

Sample Output 1

6

Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.

There are four possible choices for his workdays: Day 1,6,10, Day 1,6,11, Day 2,6,10, and Day 2,6,11.

Thus, he is bound to work on Day 6.

Sample Input 2

5 2 3
ooxoo

Sample Output 2

1
5

There is only one possible choice for his workdays: Day 1,5.

Sample Input 3

5 1 0
ooooo

Sample Output 3

There may be no days on which he is bound to work.

Sample Input 4

16 4 3
ooxxoxoxxxoxoxxo

Sample Output 4

11
16



Sample input:
11 3 2
ooxxxoxxxoo


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
# input
N, K, C = map(int, input().split())
S = input()

# process
daysL = [0]*(N+1)
daysR = [0]*(N+1)
tR = 1
tL = K
for i in range(N):
    if S[i] == 'o' and sum(daysL[max(0,i-C+1):i+1]) == 0:
        daysL[i+1] = tR
        tR += 1
    else:
        daysL[i+1] = 0

    j = N-i
    if S[j-1] == 'o' and sum(daysR[j:min(N+1,j+C)]) == 0:
        daysR[j-1] = tL
        tL -= 1
    else:
        daysR[j-1] = 0

# output
# print(daysL)
# print(daysR)
if max(daysL) == K:    
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-*-

from sys import stdin
import collections


def is_workable(K: int, C: int, S: list) -> bool:
    cnt = 0
    yasumi = 0
    for s in S:
        if yasumi > 0 or s == "x":
            yasumi -= 1
        elif s == "o":
            cnt += 1
            yasumi = C

        # check
        if cnt >= K:
            return True
    return False


def main():
    N, K, C = list(map(int, stdin.readline().split()))
    S = stdin.readline()
    # N 全体の日数
    # K 働く日数
    # C 休む中日
    # S すでに入ってる予定

    must_work = []
    if is_workable(K, C, S):
        for i, s in enumerate(S):
            if s == "x":
                continue
            if i == 0:
                S2 = "x" + S[i + 1:]
            elif i == N - 1:
                S2 = S[:i] + "x"
            else:
                S2 = S[:i] + "x" + S[i + 1:]

            if not is_workable(K, C, S2):
                must_work.append(i + 1)

        for m in must_work:
            print(m)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# input
N, K, C = map(int, input().split())
S = input()

# process
def isZero(l):
    return l.count(0) == len(l)

daysL = [0]*(N+1)
daysR = [0]*(N+1)
tR = 1
tL = K
for i in range(N):
    if S[i] == 'o' and isZero(daysL[max(0,i-C+1):i+1]):
        daysL[i+1] = tR
        tR += 1
    else:
        daysL[i+1] = 0

    j = N-i
    if S[j-1] == 'o' and isZero(daysR[j:min(N+1,j+C)]):
        daysR[j-1] = tL
        tL -= 1
    else:
        daysR[j-1] = 0

# output
# print(daysL)
# print(daysR)
if max(daysL) == K:    
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()
l = len(s) - 1
i = 0
lb = []
le = []
while i < len(s) and len(lb) < k:
    # print(i)
    if s[i] == 'o':
        lb.append(i)
        i += c + 1
        continue
    i += 1

while l > -1 and len(le) < k:
    if s[l] == 'o':
        le.append(l)
        l -= (c + 1)
        continue
    l -= 1

for j in range(0, len(lb)):
    if lb[j] in le:
        print(lb[j]+1)

Submission status: Time Limit Exceeded

Solution code:
# input
N, K, C = map(int, input().split())
S = input()

# process/output
def isZero(l):
    return l.count(0) == len(l)

daysL = [0]*(N+1)
t = 1
for i in range(N):
    if S[i] == 'o' and isZero(daysL[max(0,i-C+1):i+1]):
        daysL[i+1] = t
        t += 1
    else:
        daysL[i+1] = 0
# print(daysL)

if max(daysL) == K:
    daysR = [0]*(N+1)
    t = K
    for i in reversed(range(1,N+1)):
        if S[i-1] == 'o' and isZero(daysR[i:min(N+1,i+C)]):
            daysR[i-1] = t
            t -= 1
        else:
            daysR[i-1] = 0
    
    # print(daysR)
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = list(map(lambda x: 1 if x == 'o' else 0, input()))
b_a = []
c_k = 0
for i in range(n-1, -1, -1):
    if c_k == 0 and s[i] == 1:
        b_a.append(i)
        c_k = c
    else:
        c_k = max(c_k-1, 0)
c_k = 0
ans = []
for i in range(n):
    if c_k == 0 and s[i] == 1:
        if i in b_a:
            ans.append(i+1)
        c_k = c
    else:
        c_k = max(c_k-1, 0)
if len(ans) <= k:
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
nkc = list(map(int, input().split()))
s = input()
num = [0 for i in range(nkc[0])]
ok = [i for i in range(nkc[0]) if s[i]=='o']

def next_day(f_day, ol, c):
    nk = []
    for x in ol:
        if x-f_day >= c+1:
            nk.append(x)
    return nk

avail_dict = dict()
for i in range(len(ok)):
    avail_dict[ok[i]] = next_day(ok[i], ok[i:], nkc[2])

def workday_search(nk_list, avail_dict, depth, k):
    if len(nk_list) == 0:
        return False
    elif depth+1 == k:
        return nk_list
    else:
        days = []
        for x in nk_list:
            tmp = workday_search(avail_dict.get(x), avail_dict, depth+1, k)
            if tmp:
                for data in tmp:
                    if type(data) == int:
                        days.append([x, data])
                    else:
                        y = [x]
                        y.extend(data)
                        days.append(y)
        return days

last_day = ok[-1:][0]
workdays = workday_search([x for x in ok if (last_day-x+1) >= (nkc[1]+nkc[2]*(nkc[1]-1))], avail_dict, 0, nkc[1])

for res in workdays:
    if type(res) == int:
        num[res] += 1
    else:
        for i in res:
            num[i] += 1

for i in range(nkc[0]):
    if num[i] == len(workdays):
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
I=input().split()
N=int(I[0])
K=int(I[1])
C=int(I[2])
"""
N: 全日数
K: 働く日数
C: 労働日の最低間隔
"""
S=input()
CanWork=[]
"""
CanWork: 働ける日のみ抽出したリスト
"""
for count,i in enumerate(S):
    if (i=="o"):
        CanWork.append(count)

"""
Don_front: 前から貪欲
Don_back: 後ろから貪欲
"""
Don_front=[]
Don_back=[]
Don_front.append(CanWork[0])
Don_back.append(CanWork[-1])

for i in range(1,len(CanWork)):
    if ( len(Don_back)==K and len(Don_front)==K ):
        break
    if (CanWork[i]-Don_front[-1]>C and len(Don_front)<K):
        Don_front.append(CanWork[i])
    if (Don_back[0]-CanWork[-1-i]>C and len(Don_back)<K):
        Don_back=[CanWork[-1-i]]+Don_back

for count,i in enumerate(Don_front):
    if i==Don_back[count]:
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,k,c = list(map(int, input().split()))
s = input()
ls = list(s)

ortho = [0]*k
rever = [0]*k

a = 0
skip = []
for i in range(len(ls)):
    if a >= k: break
    if ls[i] == "o" and i not in skip:
        ortho[a] = i
        a += 1
        skip = [i+j for j in range(1, c+1)]

a = 0
skip = []
ls.reverse()
for i in range(len(ls)):
    if a >= k: break
    if ls[i] == "o" and i not in skip:
        rever[a] = i
        a += 1
        skip = [i+j for j in range(1, c+1)]

rever.reverse()
rever = [len(ls)-1-i for i in rever]

for i in range(k):
    if ortho[i] == rever[i]:
        print(ortho[i]+1)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = list(input())
countr = 0
countl = 0
switchr = 0
switchl = 0
left_greedy = [0]*len(S)
right_greedy=[0]*len(S)
#left
for l in range(len(S)):
    i = S[l]
    if switchl ==1:
        if i == 'o':
            if countl >= C:
                left_greedy[l]=1
                
                countl = 0
            else:
                countl+=1
               
        else:
            countl+=1
    else:
        if i == 'o':
            left_greedy[l]=1
            switchl+=1
#right_greedy
    r = len(S)-l-1
    i = S[r]
    if switchr ==1:
        if i == 'o':
            if countr >= C:
                right_greedy[r]=1
                
                countr = 0
            else:
                countr+=1
        else:
            countr+=1
            
    else:
        if i == 'o':
            right_greedy[r]=1
            switchr+=1
for i in range(len(S)):
    if S[i] ==  'o':
        l = left_greedy[0:i].count(1)
        r = right_greedy[i+1:len(S)].count(1)
        x = r+l
        if 1 in left_greedy[0:i][::-1]:
            if 1 in right_greedy[i+1:len(S)-1]:
                if left_greedy[0:i][::-1].index(1)+right_greedy[i+1:len(S)-1][::-1].index(1)+1 < C:
                    x+=-1
        if x < K:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = list(input())
#left_greedy
count = 0
switch = 0
left_greedy = [0]*len(S)
right_greedy=[0]*len(S)
clist = [0]*len(S)
for l in range(len(S)):
    i = S[l]
    if switch ==1:
        if i == 'o':
            if count >= C:
                left_greedy[l]=1
                clist[l] = count
                count = 0
            else:
                count+=1
                clist[l] = count
        else:
            count+=1
            clist[l] = count
    else:
        if i == 'o':
            left_greedy[l]=1
            switch+=1
#left_greedy
switch = 0
for r in range(len(S)-1, 0, -1):
    i = S[r]
    if switch ==1:
        if i == 'o':
            if count >= C:
                right_greedy[r]=1
                clist[r] = count
                count = 0
            else:
                count+=1
                clist[l] = count
        else:
            count+=1
            clist[l] = count
    else:
        if i == 'o':
            right_greedy[r]=1
            switch+=1
for i in range(len(S)):
    if S[i] ==  'o':
        l = left_greedy[0:i].count(1)
        r = right_greedy[i+1:len(S)].count(1)
        x = r+l
        if 1 in left_greedy[0:i][::-1]:
            if 1 in right_greedy[i+1:len(S)-1]:
                if left_greedy[0:i][::-1].index(1)+right_greedy[i+1:len(S)-1][::-1].index(1)+1 < C:
                    x+=-1
        if x < K:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,c = map(int,input().split())
    s = list(input())
    s = list(map((lambda x: -1 if x=='o' else 0), s))
    r = s[::-1]
    ni = 0
    cnt = 0
    while(ni<n):
        if cnt>=k:
            break
        if s[ni] == -1:
            cnt += 1
            s[ni] = cnt
            ni += c+1
        else:
            ni += 1
    ni = 0
    cnt = 0 
    while(ni<n):
        if cnt>=k:
            break
        if r[ni] == -1:
            cnt += 1
            r[ni] = cnt
            ni += c+1
        else:
            ni += 1
    r = r[::-1]
    # print(s)
    # print(r)
    for i in range(n):
        if s[i] == 0:
            continue
        def m(x):
            if x != []:
                return max(x)
            else:
                return 0
        s_len = m(s[:i])
        r_len = m(r[i+1:])
        total = s_len+r_len
        # print(i)
        # print(s_len,r_len)
        if total < k:
            print(i+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,c = map(int,input().split())
    s = list(input())
    s = list(map((lambda x: -1 if x=='o' else 0), s))
    r = s[::-1]
    ni = 0
    cnt = 0
    while(ni<n):
        if cnt>=k:
            break
        if s[ni] == -1:
            s[ni] = 1
            ni += c+1
            cnt += 1
        else:
            ni += 1
    ni = 0
    cnt = 0 
    while(ni<n):
        if cnt>=k:
            break
        if r[ni] == -1:
            r[ni] = 1
            ni += c+1
            cnt += 1
        else:
            ni += 1
    r = r[::-1]

    for i in range(n):
        if s[i] == 0:
            continue
        s_len = len([i for i in s[:i] if i==1])
        r_len = len([i for i in r[i+1:] if i==1])
        total = s_len+r_len
        # print(i)
        # print(s_len,r_len)
        if total < k:
            print(i+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = list(input())
s = list(map((lambda x: -1 if x=='o' else 0), s))
r = s[::-1]
ni = 0
cnt = 0
while(ni<n):
    if cnt>=k:
        break
    if s[ni] == -1:
        s[ni] = 1
        ni += c+1
        cnt += 1
    else:
        ni += 1
ni = 0
cnt = 0 
while(ni<n):
    if cnt>=k:
        break
    if r[ni] == -1:
        r[ni] = 1
        ni += c+1
        cnt += 1
    else:
        ni += 1
r = r[::-1]

for i in range(n):
    s_len = len([i for i in s[:i] if i==1])
    r_len = len([i for i in r[i+1:] if i==1])
    total = s_len+r_len
    # print(i)
    # print(s_len,r_len)
    if total < k:
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
Period, WorkingDay, PausePeriod = map(int, input().split())
S = input()
SReverse = S[::-1]

"""
Calculate the day that you can work the fastest and the day that you can work
the slowest. If two days coincide, that day is always a working day.
"""
earliest_days = [-1 for _ in range(Period)]
slowest_days = [-2 for _ in range(Period)]

for days in (earliest_days, slowest_days):
    i_day = 0
    if days == earliest_days:
        i_work_day = 1
        diff_from_next_work = 1
        passion_days = S
    else:
        i_work_day = WorkingDay
        diff_from_next_work = - 1
        passion_days = SReverse
    
    while 1 <= i_work_day and i_work_day <= WorkingDay:
        if passion_days[i_day] == 'o':
            days[i_day] = i_work_day
            i_work_day += diff_from_next_work
            i_day += PausePeriod
        i_day += 1

slowest_days.reverse()
for earliest_day, slowest_day in zip(earliest_days, slowest_days):
    if earliest_day == slowest_day:
        print(earliest_days.index(earliest_day) + 1)

exit()

Submission status: Time Limit Exceeded

Solution code:
Period, WorkingDay, PausePeriod = map(int, input().split())
PassionDays = input()

"""
Calculate the day that you can work the fastest and the day that you can work
the slowest. If two days coincide, that day is always a working day.
"""
earliest_days = [-1 for _ in range(Period)]
slowest_days = [-2 for _ in range(Period)]

for days in (earliest_days, slowest_days):
    
    if days == earliest_days:
        i_day = 0
        i_work_day = 1
        pause_period = PausePeriod
        diff_from_next = 1
    else:
        i_day = Period - 1
        i_work_day = WorkingDay
        pause_period = PausePeriod * (-1)
        diff_from_next = -1
    
    while 1 <= i_work_day and i_work_day <= WorkingDay:
        if PassionDays[i_day] == 'o':
            days[i_day] = i_work_day
            i_work_day += diff_from_next
            i_day += pause_period
        i_day += diff_from_next

for earliest_day, slowest_day in zip(earliest_days, slowest_days):
    if earliest_day == slowest_day:
        print(earliest_days.index(earliest_day) + 1)

exit()

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[::-1][j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt][::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

print('\n'.join(map(str, res)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18

N, K, C = map(int, input().split())
S = input()

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[::-1][j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = [N - x - 1 for x in rt[1:]][::-1]

for i in range(K):
    if lt[i] == rt[i]:
        print(lt[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
# input
N, K, C = map(int, input().split())
S = input()

# process/output
def eq(l):
    return l.count(l[0]) == len(l)

days = [0]*(N+1)

for i in range(N):
    if i+1 < N and S[i] == 'x':
        days[i+1] = days[i]
    else:
        if eq(days[max(0,i-C):i+1]):
            days[i+1] = days[i]+1
        else:
            days[i+1] = days[i]

if max(days) <= K:
    for i in range(N):
        if S[i] == 'x':
            days[i+1] = 0

    k = max(days)
    i = N
    if days[i] != k:
        i -= 1
    while k > 0:
        for j in range(max(1, i-C), i):
            if days[j] != k:
                days[j] = 0

        while days[i] in (0, k):
            i -= 1
            if i == 0:
                break

        k = days[i]
        
    # print(days)
    for k in range(1, K+1):
        if days.count(k)==1:
            print(days.index(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
n, k, c = map(int, input().split())
s = list(input())
 
index_num = [n for n, v in enumerate(s) if v == "o"]
com = list(itertools.combinations(index_num, k))
 
for co in com:
    ju = True
    for i in range(len(co)-1):
        if co[i+1] - co[i] <= c:
            ju = False
            
    if ju:
        for i in range(len(s)):
            if not i in co:
                s[i] = "x"

for i, t in enumerate(s):
    if t == "o":
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
n, k, c = map(int, input().split())
s = list(input())
 
index_num = [n for n, v in enumerate(s) if v == "o"]
com = list(itertools.combinations(index_num, k))
 
for co in com:
    ju = True
    for i in range(len(co)-1):
        if co[i+1] - co[i] <= c:
            ju = False
            
    if ju:
        for i in range(len(s)):
            if not i in co:
                s[i] = "x"
 
index_num = [n for n, v in enumerate(s) if v == "o"]
 
for i in index_num:
    print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
N,K,C = map(int,input().split())
S = list(input())
W = [i for i in range(N) if S[i]=="o" ]
# print(W)

for w in W:
    S[w] = "x"
    i = 0
    count = 0
    while i<N and count<K:
        if S[i] == "o":
            count += 1
            i += C
        i += 1
    
    # print("w,count",w,count)
    if count < K:
        print(w+1)
    
    S[w] = "o"

Submission status: Time Limit Exceeded

Solution code:
N,K,C = map(int,input().split())
S = list(input())
W = [i for i in range(N) if S[i]=="o" ]
# print(W)

for w in W:
    S[w] = "x"
    i = 0
    count = 0
    while i<N:
        if S[i] == "o":
            count += 1
            i += C
        i += 1
    
    # print("w,count",w,count)
    if count < K:
        print(w+1)
    
    S[w] = "o"

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = input()
indices = [ i for i, ltr in (enumerate(S)) if ltr == 'o']
from itertools import combinations
import numpy as np
combs = combinations(indices, K)
tcombs = None
for c in combs:
    c_ary = np.array(c)
    if ((c_ary[1:] - c_ary[:-1]) > C).all():
        if tcombs == None:
            tcombs = set(c)
        else:
            tcombs = tcombs & set(c)

for tc in tcombs:
    print(tc + 1)

Submission status: Time Limit Exceeded

Solution code:
N,K,C = map(int,input().split())
S = str(input())
works1 = 0
works2 = 0
l1 = []
l2 = []
i = 0
while i < N and works1 < K:
  if S[i] == "o":
    l1.append(i+1)
    i = i+C+1
    works1 += 1
  else:
    i = i+1
i = N-1
while i > -1 and works2 < K:
    if S[i] == "o":
      l2.append(i+1)
      i = i-C-1
      works2 = works2+1
    else:
      i = i-1

for i in range(len(l1)):
  if l1[i] in l2 :
    print(l1[i])

Submission status: Time Limit Exceeded

Solution code:
N,K,C = map(int,input().split())
S = str(input())
works1 = 0
works2 = 0
l1 = []
l2 = []
i = 0
while i < N and works1 < K:
  if S[i] == "o":
    l2.append(i+1)
    i = i+C+1
    works1 += 1
  else:
    i = i+1
i = N-1
while i > -1 and works2 < K:
    if S[i] == "o":
      l2.append(i+1)
      i = i-C-1
      works2 = works2+1
    else:
      i = i-1

l1.extend(l2)
l = [x for x in set(l1) if l1.count(x) > 1]
for i in range(len(l)):
  print(l[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,K,C=map(int,input().split())
S=input()

def check(S0):
    count=0
    index=0
    while count<K and index<N:
        if S0[index]=='o':
            count+=1
            index+=(C+1)
        else:
            index+=1
    if count==K:
        return 1
    return 0

if check(S)==0:
    print()
else:
    for i in range(N):
        if S[i]=='o':
            S0=S[:i]+'x'+S[i+1:]
            if check(S0)==0:
                print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,k,c=map(int, input().split())
s=input()
L=[0]*k
R=[0]*k
m=0
l=0
for i in range(k):
    while s[m]=="x":
        m+=1
    L[i]=m
    m+=c+1
    while s[n-l-1]=="x":
        l+=1
    R[i]=n-l-1
    l+=c+1
for i in range(k):
    if sorted(R)[i]==L[i]:
        print(L[i]+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,K,C=map(int,input().split())
  S=input()
  L=[]
  R=[]
  n=0
  rc=0
  lc=0
  while True:
    if lc==K:
      break
    if S[n]=="o":
      L+=[n+1]
      n+=C+1
      lc+=1
    else:
      n+=1
  n=N-1
  while True:
    if rc==K:
      break
    if S[n]=="o":
      R=[n+1]+R
      n-=C+1
      rc+=1
    else:
      n-=1
  for i in range(K):
    if R[i]==L[i]:
      print(R[i])
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N,K,C=map(int,input().split())
S=input()
L=[]
R=[]
n=0
rc=0
lc=0
while True:
  if lc==K:
    break
  if S[n]=="o":
    L+=[n+1]
    n+=C+1
    lc+=1
  else:
    n+=1
n=N-1
while True:
  if rc==K:
    break
  if S[n]=="o":
    R=[n+1]+R
    n-=C+1
    rc+=1
  else:
    n-=1
for i in range(K):
  if R[i]==L[i]:
    print(R[i])

Submission status: Time Limit Exceeded

Solution code:
N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

f_count = 0
b_count = 0
f_rest = 0
b_rest = 0
S_len = len(S)

for i in range(S_len):
    if f_count == K and b_count == K:
        break

    if f_count < K:
        if S[i] == "o" and f_rest == 0:
            f_rest += C
            f_count += 1
            F_list.append(i+1)
        else:
            if f_rest > 0:
                f_rest -= 1
    if b_count < K:
        if S[-(i+1)] == "o" and b_rest == 0:
            b_rest += C
            b_count += 1
            B_list.append(S_len-i)
        else:
            if b_rest > 0:
                b_rest -= 1


for i in F_list:
    if i in B_list:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x in L:
    if x in R[bisect_left(R,x):]:
        print x+1

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C


for x in L:
    if x in R:
        print x+1

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = input()

work_date = []

# 先詰めで出勤する場合
pw = 0

for d in range(K):

    w = S[pw:].index('o') + pw
    work_date.append(w)

    # 次出勤する可能性がある、最初の日を探す
    pw = w + C + 1
    
# 後詰めで出勤する場合
work_date_l = []

Sr = "".join(list(reversed(S)))
pw = 0

for d in range(K):

    w = Sr[pw:].index('o') + pw
    work_date_l.append((N-1)-w)

    # 次出勤する可能性がある、最初の日を探す
    pw = w + C + 1

work_date_l.sort()
    
for i in range(K):
    if work_date[i] == work_date_l[i]:
        print(work_date[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def greedy_search(K, C, workable, shift = 1):
    workable = workable[::shift]
    if workable == []:return []
    work_day = 1
    pre_day = workable[0]
    work_list = [workable[0]]
    if work_day == K:
        return work_list
    if workable[1:] == []:
        return []
    for work in workable[1:]:
        if shift*(pre_day + C *shift) >= work*shift:
            continue
        pre_day = work
        work_day += 1
        work_list.append(work)
        if work_day == K:
            return work_list
    return []

def extract(S):
    ret = []
    for idx, s in enumerate(S, 1):
        if s == 'o':
            ret.append(idx)
    return ret

if __name__ == '__main__':
    N, K, C = list(map(int, input().split()))
    S = list(input())
    base = extract(S)
    left = greedy_search(K,C,base,shift=1)
    right= greedy_search(K,C,base,shift=-1)[::-1]
    #print(base)
    #print(left)
    #print(right)
    for i in base:
        left_k = len(left)
        left_margin = left[-1] if left is not [] else -10**10
        for left_idx in range(len(left)):
            if left[left_idx] >= i:
                left_k = left_idx
                left_margin = left[left_idx-1] if left_idx != 0 else -10**10
                break
        right_k = 0
        right_margin = 10 ** 10
        for right_idx in range(len(right)):
            if right[right_idx] > i:
                right_k = len(right) - right_idx
                right_margin = right[right_idx]
                break
        kk = left_k + right_k
        if right_margin - left_margin <= C:
            kk -= 1
        if kk < K:
            print(i)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

count = 0
add_count = 0
S_len = len(S)
while count < S_len and add_count < K:
    if S[count] == "o":
        add_count += 1
        F_list.append(count+1)
        count += C+1
    else:
        count += 1

count = 0
add_count = 0

while count < S_len and add_count < K:
    if S[-(count+1)] == "o":
        add_count += 1
        B_list.append(S_len-count)
        count += C+1
    else:
        count += 1


for i in F_list:
    if i in B_list:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import time

N, K, C = list(map(int, input().split()))
S = list(input())

F = []
L = []

# t1 = time.time()
# for i in range(N):
#     if S[i] == 'o':
#         if len(F) == 0:
#             F.append(i)
#         elif F[-1] + C < i:
#             F.append(i)
#     if len(F) >= K:
#         break
# print(F)
# t2 = time.time()
i = 0
while len(F) < K:
    if S[i] == 'o':
        if len(F) == 0:
            F.append(i)
        elif F[-1] + C < i:
            F.append(i)
    i += 1
# print(F)
# t3 = time.time()

# print(t2 - t1, t3 - t2)

i = N - 1
while len(L) < K:
    if S[i] == 'o':
        if len(L) == 0:
            L.append(i)
        elif L[-1] - C > i:
            L.append(i)
    i -= 1

[print(i + 1) for i in F if i in L]

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()
left_dp = []
right_dp = []

i = 0
while len(left_dp)<k:
    if s[i] == "o":
        left_dp.append(i+1)
        i += c+1
    else: i += 1
        
i = n-1
while len(right_dp)<k:
    if s[i] == "o":
        right_dp.append(i+1)
        i -= c+1
    else: i -= 1

for i in left_dp:
    for j in right_dp:
        if i == j: 
            print(i)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
N,K,C=map(int,input().split())
S=input()
S_R=S[::-1]
L=[0]*N
R=[0]*N
L_cnt=1
R_cnt=K
for i in range(N):
	if S[i]=="o" and L_cnt<=K:
		if L_cnt==1:
			L[i]=1
			L_cnt+=1
		elif i>(L.index(L_cnt-1)+C):
			L[i]=L_cnt
			L_cnt+=1
	if S_R[i]=="o" and R_cnt>=1:
		if R_cnt==K:
			R[N-1-i]=K
			R_cnt-=1
		elif (N-1-i)<(R.index(R_cnt+1)-C):
			R[N-1-i]=R_cnt
			R_cnt-=1	
result=[]
for i in range(N):
	if L[i]!=0 and R[i]!=0 and L[i]==R[i]:
		print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = list(map(int, input().split(" ")))
S = input()
S_list = [i for i in S]

F_list = []
B_list = []
count = 0
len_S = len(S_list)
for j in range(K):
    for i in range(count, len_S):
        if S_list[i] == "o":
            F_list.append(i+1)
            count += C+1
            break
        else:
            count += 1

#S_list = S_list[::-1]

count = 0
for j in range(K):
    for i in range(count, len_S):
        if S_list[-(i+1)] == "o":
            B_list.append(len_S-i)
            count += C+1
            break
        else:
            count += 1

for i in F_list:
    if i in B_list:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, K, C = map(int, sys.stdin.readline().rstrip().split())
S = sys.stdin.readline().rstrip()

L = [0] * K
R = [0] * K
candidates = [i + 1 for i in range(N) if S[i] == 'o']

L[0] = candidates[0]
R[0] = candidates[-1]
cL = L[0]
cR = R[0]
kL = 1
kR = 1
for li in range(len(candidates)):
    ri = -(li + 1)
    if candidates[li] - cL > C and kL < K:
        L[kL] = cL = candidates[li]
        kL += 1
    if cR - candidates[ri] > C and kR < K:
        R[kR] = cR = candidates[ri]
        kR += 1
    if kL == kR == 0:
        break

if kL < K or kR < K:
    sys.exit()

for l in L:
    if l in R:
        print(l)