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:
N,K,C = map(int,input().split())
S = input()
se_ = set(range(N))

import itertools

for i in itertools.combinations(range(N),K):
    li_ = list(i)
    for k in range(K-1):
        if li_[k+1]-li_[k]<=C or S[li_[k]]=="x" or S[li_[k+1]]=="x":
            break
    else:
        se_ = se_ & set(i)

for i in se_:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,K,C = inputIL()
S = inputS()

L = []

i = 0
c = 0
while i<N:
  if c == K:
    break
  if S[i]=="o":
    L.append(i)
    c += 1
    i += C+1
  else:
    i += 1

R = []

i = N-1
c = 0
while i>=0:
  if c == K:
    break
  if S[i]=="o":
    R.append(i)
    c += 1
    i -= C+1
  else:
    i -= 1


for i in range(K):
  if L[i] == R[::-1][i]:
    print(L[i]+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,K,C = inputIL()
S = inputS()

L = []

i = 0
c = 0
while i<N and c<K:
  if S[i]=="o":
    L.append(i)
    c += 1
    i += C+1
  else:
    i += 1

R = []

i = N-1
c = 0
while i>=0 and c<K:
  if S[i]=="o":
    R.append(i)
    c += 1
    i -= C+1
  else:
    i -= 1

for i in range(K):
  if L[i] == R[::-1][i]:
    print(L[i]+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,K,C = inputIL()
S = inputS()

L = []

i = 0
while i<N and len(L)<K:
  if S[i]=="o":
    L.append(i)
    i += C+1
  else:
    i += 1

R = []

i = N-1
while i>=0 and len(R)<K:
  if S[i]=="o":
    R.append(i)
    i -= C+1
  else:
    i -= 1

for i in range(K):
  if L[i] == R[::-1][i]:
    print(L[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, k, c = map(int, input().split())
s = input()
a = []
for i in range(n):
    if s[i] == 'o':
        a.append(i+1)

ans = []
for i in range(len(a)):
    cur = 10 ** 10
    flg = False
    for j in range(k):
        idx = bisect.bisect_left(a, cur - c) - 1
        if idx == i:
            idx -= 1
        if idx < 0:
            flg = True
            break
        cur = a[idx]


    if flg:
        ans.append(a[i])

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, k, c = inp()
        st = inst()
        front, end = [], []
        def get(now, ans):
            if len(ans) == k:
                return
            for i in range(now, n):
                if st[i]=='o':
                    ans.append(i+1)
                    return get(i+1+c, ans)
        get(0, front)
        st = st[::-1]
        get(0, end)
        for i in range(len(end)):
            end[i] = n-end[i]+1
        end.sort()
        if len(front)!=k or len(end)!=k:
            return
        ans = []
        # print front, end
        for i in range(k):
            if front[i] == end[i]:
                ans.append(front[i])
        if ans:
            print '\n'.join(map(str, ans))

my_main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import math
import bisect
import re

n, k, c = map(int, stdin.readline().strip().split())
s = stdin.readline().strip()

arr1 = []
arr2 = []

rest = -1
cnt = k
for i in range(len(s)):
    if rest < 0 and s[i] == 'o':
        rest = c
        cnt -= 1
        arr1.append(i + 1)
    rest -= 1
    if cnt <= 0:
        break

rest = -1
cnt = k
for i in range(len(s)-1,-1,-1):
    if rest < 0 and s[i] == 'o':
        rest = c
        cnt -= 1
        arr2.append(i + 1)
    rest -= 1
    if cnt <= 0:
        break

for each in arr1:
    if each in arr2:
        stdout.writelines('%d\n' % each)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K, C = map(int, sys.stdin.readline().split())
S = list(sys.stdin.readline().rstrip())
O = [i for i, x in enumerate(S) if x == "o"]
S = [O[0]]
T = [O[-1]]
a = 0
for j in O:
    if len(S) == K:
        break
    if j > S[a] + C:
        S.append(j)
        a += 1
        

b = -1
for k in O[::-1]:
    if len(T) == K:
        break
    if k < T[b] - C:
        T.append(k)
        b -= 1
        


for m in range(K):
    if S[m] == T[::-1][m]:
        print(S[m] + 1)

Submission status: Time Limit Exceeded

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

def apply( k, c, s ):
    cnt = 0
    date = 0
    while date < len( s ):
        if s[ date ] == "x":
            date = date + 1
        elif s[ date ] == "o":
            cnt = cnt + 1
            date = date + c
            date = date + 1
        else:
            return False
    if cnt < k:
        return False
    else:
        return True
    
date = 0    
while date < len( s ):
    #print( s[:date] + s[date + 1:] )
    if not apply( k, c, s[:date] + s[date + 1:] ):
        print( date + 1 )
        date = date + c
        date = date + 1
    else:
        date = date + 1

Submission status: Time Limit Exceeded

Solution code:
N,K,C=map(int,input().split())
S=input()
i=0
d1=[-1]*N
for k in range(K):
    try:
        i+=S[i:].index('o')
    except:
        break
    d1[i]=k
    i+=C+1
i=0
d2=[-1]*N
for k in range(K-1,-1,-1):
    try:
        i+=S[N-1-i::-1].index('o')
    except:
        break
    d2[N-1-i]=k
    i+=C+1
print(*[i+1 for i in range(N) if d1[i]==d2[i]>=0],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,K,C=map(int,input().split())
S=input()
i=0
d1=[-1]*N
for k in range(K):
    try:
        i=S.index('o',i)
    except:
        break
    d1[i]=k
    i+=C+1
i=0
d2=[-1]*N
for k in range(K-1,-1,-1):
    try:
        i=S[::-1].index('o',i)
    except:
        break
    d2[N-1-i]=k
    i+=C+1
print(*[i+1 for i in range(N) if d1[i]==d2[i]>=0],sep='\n')

Submission status: Time Limit Exceeded

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

S = input()

L = [0 for i in range(K)]
R = [0 for i in range(K)]


rest = 0
work = 0

for i in range(N):
    if rest == 0:
        if S[i] == 'o':
            L[work] = i+1
            rest = C
            work += 1
            if work == K:
                break
    else:
        rest -= 1

rest = 0
work = 0

for i in range(N-1,-1,-1):
    if rest == 0:
        if S[i] == 'o':
            R[work] = i+1
            rest = C
            work += 1
            if work == K:
                break
    else:
        rest -= 1

for i in range(K):
    if L[i] in R:
        print(L[i])

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k, c = map(int, input().split())
s= list(input())
#n = 100000
#k = 1000
#c = 1
#s = list()
for i in range(100000):
    s.append('o')

sans = copy.copy(s)

if (c == 0):
    cnt = 0
    for i in range(n):
        if(s[i] == 'o'):
            cnt+=1
    if not(cnt == k):
        for i in range(n):
            sans[i] = 'x'
else:
    tmps = copy.copy(s)
    for i in range(n):
        if(sans[i]=='o'):
            tmps[i]='x'
            cnt = 0
            yasu = 0
            for j in range(n):
                if(tmps[j]=='o' and yasu == 0):
                    cnt+=1
                    yasu=c
                else:
                    if(yasu > 0):
                        yasu-=1
                    tmps[j] = 'x'
            if(cnt >= k):
                for j in range(i,n):
                    if(tmps[j] == 'x'):
                        sans[j]='x'
            tmps = copy.copy(s)
for i in range(n):
    if(sans[i] == 'o'):
        print(i+1)

Submission status: Time Limit Exceeded

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

if (c == 0):
    cnt = 0
    for i in range(n):
        if(s[i] == 'o'):
            cnt+=1
    if not(cnt == k):
        for i in range(n):
            sans[i] = 'x'
else:
    for i in range(n):
        tmps = copy.copy(s)
        if(sans[i]=='o'):
            tmps[i]='x'
            cnt = 0
            yasu = 0
            for j in range(n):
                if(tmps[j]=='o' and yasu == 0):
                    cnt+=1
                    yasu=c
                else:
                    if(yasu > 0):
                        yasu-=1
                    tmps[j] = 'x'
            if(cnt >= k):
                for j in range(i,n):
                    if(tmps[j] == 'x'):
                        sans[j]='x'
for i in range(n):
    if(sans[i] == 'o'):
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k, c = map(int, input().split())
s= list(input())
sans = copy.copy(s)
for i in range(n):
    tmps = copy.copy(s)
    if(sans[i]=='o'):
        tmps[i]='x'
        cnt = 0
        yasu = 0
        for j in range(n):
            if(tmps[j]=='o' and yasu == 0):
                cnt+=1
                yasu=c
            else:
                if(yasu > 0):
                    yasu-=1
                tmps[j] = 'x'
        if(cnt >= k):
            for j in range(n):
                if(tmps[j] == 'x'):
                    sans[j]='x'
for i in range(n):
    if(sans[i] == 'o'):
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,k,c=map(int,input().split())
s=input()
l=len(s)
cand=[]
for i in range(l):
    if s[i]=='o':
        cand.append(i+1)
        cnt1=[0]*(n+c+2)
        cnt2=[0]*(n+c+2)

for i in range(l):
    if s[i]=='o':
        cnt1[i+1]=max(cnt1[i],cnt1[i-c]+1)
    else:
        cnt1[i+1]=cnt1[i]
for i in range(l-1,-1,-1):
    if s[i]=='o':
        cnt2[i+1]=max(cnt2[i+2],cnt2[i+c+2]+1)
    else:
        cnt2[i+1]=cnt2[i+2]
ans=[]
for i in range(len(cand)):##嘘に見える
    tmp=cand[i]
    if cnt1[tmp-1]+cnt2[tmp+1]<k:
        ans.append(tmp)
for val in ans:
    print(val)

Submission status: Time Limit Exceeded

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

ch1=[0]*n
ch2=[0]*n
i=0
while i < n:
    if s[i] == 'o':
        ch1[i] = 1
        i+=c
    i+=1
    if sum(ch1) >= k:break

i=n-1
while i > -1:
    if s[i] == 'o':
        ch2[i] = 1
        i-=c
    i-=1
    if sum(ch2) >= k:break


ans = []
for i in range(n):
    if ch1[i] and ch2[i]:
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
N,K,C = map(int ,input().split())
S = input()
 
 
selectable_day = [i + 1 for i in range(len(S)) if S[i] == 'o']
 
combination = list(itertools.combinations(selectable_day,K))
 
collect_combination = []
collect_number = []
 
for i in combination:
    para = 0
    for j in range(K-1):
        if i[j+1]-i[j] > C:
            continue;
        else :
            para = 1
            break;
    if para == 0:
        collect_combination.append(list(i))
        collect_number.extend(list(i))
 
collect_number = list(set(collect_number))
 
if len(collect_combination) == 1:
    for i in range(K):
        print(collect_combination[0][i])
elif len(collect_combination) == 0:
    exit();
else :
    for i in collect_number:
        para = 0
        for j in collect_combination:
            if i in j:
                continue;
            else :
                para = 1
        if para == 0:
            print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


selectable_day = [i + 1 for i in range(len(S)) if S[i] == 'o']

combination = list(itertools.combinations(selectable_day,K))

collect_combination = []
collect_number = []

for i in combination:
    para = [0 if i[j+1]-i[j] > C else 1 for j in range(K-1)]
    if 1 not in para:
        collect_combination.append(list(i))
        collect_number.extend(list(i))

collect_number = list(set(collect_number))

if len(collect_combination) == 1:
    for i in range(K):
        print(collect_combination[0][i])
elif len(collect_combination) == 0:
    exit();
else :
    for i in collect_number:
        para = [0 if i in j else 1 for j in collect_combination]
        if 1 not in para:
            print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


selectable_day = [i + 1 for i in range(len(S)) if S[i] == 'o']

combination = list(itertools.combinations(selectable_day,K))

collect_combination = []
collect_number = []

for i in combination:
    para = 0
    for j in range(K-1):
        if i[j+1]-i[j] > C:
            continue;
        else :
            para = 1
            break;
    if para == 0:
        collect_combination.append(list(i))
        collect_number.extend(list(i))

collect_number = list(set(collect_number))

if len(collect_combination) == 1:
    for i in range(K):
        print(collect_combination[0][i])
elif len(collect_combination) == 0:
    exit();
else :
    for i in collect_number:
        para = 0
        for j in collect_combination:
            if i in j:
                continue;
            else :
                para = 1
        if para == 0:
            print(i)

Submission status: Time Limit Exceeded

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

l = [0]*k
l[0] = s.find("o")+1
r = [0]*k
r[k-1] = s.rfind("o")+1

x = 1
y = k - 2

for i in range(1,n):
    if i > l[x-1] + c - 1 and s[i] == "o" and x < k:
        l[x] = i + 1
        x += 1
    j = n - 1 - i
    if j < r[y+1] - c - 1 and s[j] == "o" and y >= 0:
        r[y] = j + 1
        y -= 1

for i in range(k):
    if l[i] == r[i]:
        ans += str(l[i]) + "\n"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, c = map(int,input().split())
    s = input()
    schedule = [w == "o" for w in s]
    left = []
    l_day = 0
    right = []
    r_day = n - 1
    while len(left) < k:
        if schedule[l_day]:
            left.append(l_day)
            l_day += c
        l_day += 1

    while len(right) < k:
        if schedule[r_day]:
            right = [r_day] + right
            r_day -= c
        r_day -= 1


    for i in range(k):
        if left[i] == right[i]:
            print(left[i] + 1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, c = map(int,input().split())
    s = input()
    schedule = [w == "o" for w in s]
    left = []
    l_day = 0
    right = []
    r_day = n - 1
    for i_1 in range(n):
        if schedule[l_day]:
            left.append(l_day)
            l_day += c
        l_day += 1
        if len(left) == k:
            break

    for i_2 in range(n):
        if schedule[r_day]:
            right = [r_day] + right
            r_day -= c
        r_day -= 1
        if len(right) == k:
            break
    for i in range(k):
        if left[i] == right[i]:
            print(left[i] + 1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = list(input())
list_o = []
for i in range(N):
  if S[i] == "o":
    list_o.append(i)
#oの日だけをピックアップ

bef1 = -2 * 10 ** 5
worklist1 = []
for num1 in list_o:
  if num1 - bef1 > C:
    worklist1.append(num1)
    bef1 = num1
#worklist1の中に、一番単純に思いつく組み合わせを入れる

if len(worklist1) < K:
  exit()
#一個も組み合わせなかったら

else:
  for num2 in worklist1:
    bef2 = -2 * 10 ** 5
    list_o.remove(num2)
    worklist2 = []
    for num3 in list_o:
      if num3 - bef2 > C:
        worklist2.append(num3)
        bef2 = num3
    #ひとつ抜いた状態でworklist2を作ってみる
    list_o.append(num2)
    list_o.sort()
    #list_oを元どおりに
    if len(worklist2) < K:
      print(num2 + 1)
#worklist1の中身をひとつずつ抜いてみて、他に組み合わせが作れないならその項は不可欠だから出力

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, c = map(int,input().split())
    s = input()
    schedule = [w == "o" for w in s]
    for i in range(n):
        if not schedule[i]:
            continue
        det(schedule,i,n,k,c)

def det(schedule,i,n,k,c):
    ins = schedule.copy()
    ins[i] = False
    count = 0
    date = 0
    for _ in range(n):
        if ins[date]:
            count += 1
            date += c
        date += 1
        if date >= n:
            break
    if count < k:
        print(i + 1)






if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
DATA = """
16 4 3
ooxxoxoxxxoxoxxo
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, K, C = [int(i) for i in get_line().strip().split(" ")]
S = get_line()
aa = set(range(N))
def Sub(n, s, l):
	if n >= K:
		global aa
		aa &= set(l)
		return 

	for i in range(s, N):
		if S[i] == "x":
			continue
		l[n] = i 
		Sub(n+1, i+C+1, l)
		l[n] = None
	return

class Info(object):
	def __init__(self, n, s, l):
		self.n = n
		self.s = s
		self.l = l
	
	def Data(self):
		return self.n, self.s, self.l

ret = [Info(0, 0, [None]*K)]
for _ in range(K):
	ret2 = []
	for r in ret:
		n, s, l = r.Data()
		for i in range(s, N):
			if S[i] == "x":
				continue
			ll = l.copy()
			ll[n] = i
			ret2.append(Info(n+1, i+C+1, ll))
	ret = ret2
#Sub(K-2, 0, [None]*K)
for r in ret:
	#print (r.Data())
	aa &= set(r.l)

for a in aa:
	print (a+1)

Submission status: Time Limit Exceeded

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

fastest = deque([])
latest = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        print(fastest[i])

Submission status: Time Limit Exceeded

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

fastest = deque([])
latest = deque([])
ans = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        ans.append(fastest[i])

print(*ans)

Submission status: Time Limit Exceeded

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

fastest = deque([])
latest = deque([])
ans = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] != 'o':
        date += 1
        if date > N:
            break
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] != 'o':
        date += 1
        if date > N:
            break
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        ans.append(fastest[i])

print(*ans)

Submission status: Time Limit Exceeded

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

fastest = deque([])
latest = deque([])
ans = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] != 'o':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] != 'o':
        date += 1
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        ans.append(fastest[i])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N_K_C = [int(input_) for input_ in input().split(" ")]
N = N_K_C[0]
K = N_K_C[1]
C = N_K_C[2]
    
tick_cross = input()
    
def find_earliest_work_day(nth, C, tick_cross):
    """
    Find the earliest day in all possible days for the n-th work day.
    
    Parameters:
    nth (int): The number indicating how many days he's worked.
    C (int): Minimum interval between the previous work day and the 
             next work day.
    tick_cross (str): The character string of days he can go to work.
             
    Returns:
    int: The earliest day in all possible days for the n-th work day.
    """
    N = len(tick_cross)
        
    day = 0
    counter = 0
    while True:
        if tick_cross[day] == "o":
            counter += 1
            if counter == nth:
                return day + 1
            else:
                day += C + 1
        else:
            day += 1
            
        if day > N:
            raise IndexError
    
def find_latest_work_day(nth, C, tick_cross): 
    """
    Find the latest day in all possible days for the n-th work day.
    
    Parameters:
    nth (int): The number indicating how many more days he must work.
    C (int): Minimum interval between the previous work day and the 
             next work day.
    tick_cross (str): The character string of days he can go to work.
             
    Returns:
    int: The latest day in all possible days for the n-th work day.
    """
    
    N = len(tick_cross)
        
    day = N - 1
    counter = 0
    while True:
        if tick_cross[day] == "o":
            counter += 1
            if counter == (nth + 1):
                return day + 1
            else:
                day -= C + 1
        else:
            day -= 1
            
        if day < 0:
            raise IndexError
                
for nth_work_day in range(1, K+1):
    try:
        earliest_work_day = find_earliest_work_day(nth_work_day,
                                                   C, tick_cross)
        latest_work_day = find_latest_work_day(K - nth_work_day,
                                               C, tick_cross)
    except IndexError:
        break
    else:
        if earliest_work_day == latest_work_day:
            print(earliest_work_day)

Submission status: Time Limit Exceeded

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

l=[]
r=[]
i=0
j=n-1
while len(l)<k:
    if s[i]=='x':
        i+=1
    if s[i]=='o':
        l.append(i+1)
        i+=c+1
while len(r)<k:
    if s[j]=='x':
        j-=1
    if s[j]=='o':
        r.insert(0,j+1)
        j-=c+1
"""
ここまでで、lには「最速でその日に仕事ができる」
rには「遅くともその日までには仕事しないといけない」
というリストができます。
print(l)
print(r)
"""
for _ in range(len(l)):
    if l[_]==r[_]:
        print(l[_])

Submission status: Time Limit Exceeded

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

l1 = [float("inf")]*n
l2 = [float("inf")]*n

cnt1 = 0
i = 0
while cnt1 < k and i<n:
    if s[i] == "o":
        l1[i] = cnt1 + 1
        i += c + 1
        cnt1 += 1
    else:
        i += 1

cnt2 = k
i = n-1
while cnt2 != 0 and i>=0:
    if s[i] == "o":
        l2[i] = cnt2
        i -= c + 1
        cnt2 -= 1
    else:
        i -= 1

for i in range(1,k+1):
    if l1.index(i) == l2.index(i):
        print(l1.index(i) + 1)

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)
daysL = [0]
daysR = [0]
tL = 1
tR = K
for i in range(N):
    if S[i] == 'o' and sum(daysL[max(0,i-C+1):]) == 0:
        daysL.append(tL)
        tL += 1
    else:
        daysL.append(0)

    if S[N-i-1] == 'o' and sum(daysR[max(0,i-C+1):]) == 0:
        daysR.append(tR)
        tR -= 1
    else:
        daysR.append(0)

# output
# print(daysL)
# print(daysR)
if tL == K+1:    
    for i in range(N):
        if daysL[i+1] > 0 and daysL[i+1] == daysR[N-i]:
            print(i+1)