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: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k,c = m()

s = list(input())[:-1]


dp0 = [-1 for i in range(k)]
dp1 = [-1 for i in range(k)]
co = 0
po = 0
for i in range(n):
    if co == 0:
        if s[i] == "o":
            dp0[po] = i
            if po == k-1:
                break
            po += 1
            co = c
    else:
        co -= 1

co = 0

po = k-1

for i in range(n-1,-1,-1):
    if co == 0:
        if s[i] == "o":
            dp1[po] = i
            if po == 0:
                break
            co = c
            po -= 1

    else:
        co -= 1

for i in range(k):
    if dp0[i] == dp1[i] and dp0[i] != -1:
        print(dp0[i]+1)

Submission status: Accepted

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

def solve(S):
    A = []
    for i, s in enumerate(S):
        if s == "o" and (not A or A[-1] + C < i):
            A.append(i)
        if len(A) >= K:
            break
    return A

L = solve(S)
R = reversed(solve(reversed(S)))

print("\n".join(str(l + 1) for l, r in zip(L, R) if l == N - r - 1))

Submission status: Accepted

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

ans = []
cnt = 0
kcn = 0
for i,x in enumerate(s[::-1]):
    i = n - i - 1
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        ans.append(i)

cnt = 0
j = len(ans) - 1
kcn = 0
for i,x in enumerate(s):
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        if ans[j] == i:
            print(i+1)
        j -= 1

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,k,c=map(int,input().split())
S=input()
A=[]
for i in range(n):
    if S[i]=="o":
        A.append(i)

B=[]
C=[]
now=-1
for a in A:
    if now==-1:
        C.append(a)
        now=a
    else:
        if now+c>=a:
            C.append(a)
        else:
            B.append(C)
            C=[]
            C.append(a)
            now=a
if C:
    B.append(C)
    
b=len(B)

if b==k:
    Ans=[]
    for i in range(b):
        T=B[-1-i]
        l=len(T)
        if l==1:
            chk=T[0]
            Ans.append(T[0])
            continue
        if i==0:
            chk=T[-1]
            continue
        cnt=0 #勤務可能が1日しかないかチェック
        for t in T:
            if t+c<chk: #後ろの勤務可能最終日と比較
                now=t
                cnt+=1
            else:
                break
        chk=now
        if cnt==1:
            Ans.append(T[0])

    Ans.sort()
    for ans in Ans:
        print(ans+1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
s2 = s
s += "x"*c
s2 = "x"*c+s2
k2 = k
kans = k
left = []
i = 0
while i < n:
  if s[i] == "o":
    left.append(i+1)
    i += c
  i += 1

right = []
i = len(s2)-1
while i >= c:
  if k2 == 0:
    break
  if s2[i] == "o":
    right.append(i+1-c)
    k2 -= 1
    i -= c
  i -= 1
if len(left) == kans:
  ans = sorted(list(set(left) & set(right)))
  for i in ans:
    print(i)
else:
  exit()

Submission status: Accepted

Solution code:
import copy
N,K,C = list(map(int, input().split()))
S = list(input())
count = 0
mae = [0]*K
ushiro = [0]*K
hi = 0
youso = 0
S_copy = copy.deepcopy(S)

while True:
    if S_copy[hi] == 'o':
        mae[youso] = hi+1
        youso += 1
        if youso == K:
            break
        for i in range(C):
            if hi+1+i <= N-1:
                S_copy[hi+1+i] = 'x'
    hi += 1

hi = 0
youso = 0
S_copy = copy.deepcopy(S)
S_copy.reverse()

while True:
    if S_copy[hi] == 'o':
        ushiro[youso] = hi-1
        youso += 1
        if youso == K:
            break
        for i in range(C):
            if hi+1+i <= N-1:
                S_copy[hi+1+i] = 'x'
    hi += 1

ushiro = list(map(lambda x: N-x-1, ushiro))
ushiro.reverse()

ans = []

for j in range(len(mae)):
    if mae[j] == ushiro[j]:
        ans.append(mae[j])

if ans:
    for j in range(len(ans)):
        print(ans[j])

Submission status: Accepted

Solution code:
def main():
    n,k,c=map(int,input().split())
    S=list(input().strip())
    if n==1:
        Ans=[1]
    else:
        A=[]
        for i,s in enumerate(S):
            if s=='o':
                A.append(i+1)
        l=len(A)
        L=[0]*k
        L[0]=A[0]
        prev=A[0]
        cnt=1
        for a in A[1:]:
            if cnt==k:
                break
            if a-prev>c:
                prev=a
                L[cnt]=a
                cnt+=1
        R=[0]*k
        R[-1]=A[-1]
        prev=A[-1]
        cnt=1
        for a in reversed(A[:-1]):
            if cnt==k:
                break
            if prev-a>c:
                prev=a
                R[k-cnt-1]=a
                cnt+=1
        Ans=[]
        #print(L,R)
        for i in range(k):
            if L[i]==R[i]:
                Ans.append(L[i])
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

l=[0]*N
la=[0]*N
i=0
c=0
while True:
    if S[i]=="o":
        l[i]=1
        i+=C
        c+=1
    i+=1
    if i>=N:
        break

if c>K:
    exit()

i=N-1
c=0

while True:
    if S[i]=="o":
        la[i]=1
        i-=C
        c+=1
    i-=1
    if c==K:
        break
    
for i in range(N):
    if l[i]==1 and la[i]==1:
        print(i+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,K,C = map(int,input().split())
S = input()

i=0
forward = set()
while N>i:
    if S[i] == "o":
        forward.add(i)
        i+=C+1
    else:
        i+=1

if len(forward) != K:
    exit()

i=N-1
backward = set()
while i>=0:
    if S[i] == "o":
        backward.add(i)
        i-=C+1
    else:
        i-=1
    
# print(forward, backward)
isect = list(forward&backward)
for i in sorted(isect):
    print(i+1)

Submission status: Accepted

Solution code:
I = lambda : list(map(int,input().split()))
n,k,m = I();p=0;l=k
s=input();x=[];y=[]
for i in range(n):
    if s[i]=='o' and p==0:
        k-=1;x.append(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
p=0;k=l
for i in range(n-1,-1,-1):
    if s[i]=='o' and p==0:
        k-=1;y.append(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
y=y[::-1]
for i in range(len(x)):
    if x[i]==y[i]:
        print(x[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,k,c = map(int, input().split())
S = input()
inds = [i for i,s in enumerate(S) if s == "o"]
ls = []
prev = -100000000
cnt = 0
for i in inds:
    if i - prev > c:
        ls.append(i)
        prev = i
        cnt += 1 
    if cnt > k:break

rs = []
cnt = 0
prev = 1000000000
for i in inds[::-1]:
    if prev - i > c:
        rs.append(i)
        prev = i    
        cnt += 1 
    if cnt > k:break

ans = []
cnt = 0
for l,r in zip(ls,rs[::-1]):
    if l == r:
        print(l+1)
        cnt += 1
if cnt == 0:
    print()

Submission status: Accepted

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

# why are these variables named "dp"?
dp1 = [10**6] * K
dp2 = [0] * K

i = 0
dp_ind = 0
while i < N:
    if S[i] == "o":
        dp1[dp_ind] = i
        dp_ind += 1
        if dp_ind == K:
            break
        i += C + 1
        continue
    i += 1

i = N - 1
dp_ind = K - 1
while i >= 0:
    if S[i] == "o":
        dp2[dp_ind] = i
        dp_ind -= 1
        if dp_ind == -1:
            break
        i -= C + 1
        continue
    i -= 1
for a, b in zip(dp1, dp2):
    if a == b:
        print(a+1)

Submission status: Accepted

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


count = 0
i = 0
ansleft = set()
while i < n:
    if s[i] == "o":
        ansleft.add(i+1)
        i += c+1
        count += 1
    else:
        i += 1

if count >= k+1:
    sys.exit()


ansright = set()
s = s[::-1]
i = 0
while i < n:
    if s[i] == "o":
        ansright.add(n-i)
        i += c+1
    else:
        i += 1

ans = ansright&ansleft
ans = list(ans)
ans.sort()
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from bisect import *
from collections import *

N, K, C = map(int, input().split())
S = input()
T = [i for i, x in enumerate(S, 1) if x == 'o']
sl = deque()
sr = deque()
i = 0
while len(sl) < K:
    sl.append(T[i])
    i = bisect_right(T, T[i]+C)
i = len(T)-1
while len(sr) < K:
    sr.appendleft(T[i])
    i = bisect_left(T, T[i]-C)-1
for x, y in zip(sl, sr):
    if x == y:
        print(x)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s="?"+input()
fwd=set()
now=1
while now<=n:
	if s[now]=="o":
		fwd.add(now)
		now+=c+1
	else:
		now+=1
bwd=set()
now=n
while now>=1:
	if s[now]=="o":
		bwd.add(now)
		now-=c+1
	else:
		now-=1
if len(fwd)==k:
	print(*sorted(list(fwd&bwd)),sep="\n")
else:
	exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k,c = LI()
s = input()
l,r = [0]*k, [0]*k
i = 0
cnt = 0
while i < n:
    if s[i] == 'o':
        if cnt >= k:
            quit()
        l[cnt] = i
        cnt += 1
        i += c
    i += 1
i = n-1
cnt = k-1
while i >= 0:
    if s[i] == 'o':
        if cnt < 0:
            quit()
        r[cnt] = i
        cnt -= 1
        i -= c
    i -= 1
for i in range(k):
    if l[i] == r[i]:
        print(l[i]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

if c == 0:
    if s.count("o") == k:
        for i in range(n):
            if s[i] == "o":
                print(i + 1)
    exit()

left = []
i = 0
while i < n:
    if s[i] == "o":
        left.append(i)
        i += c
    i += 1

right = []
i = n - 1
while i >= 0:
    if s[i] == "o":
        right.append(i)
        i -= c
    i -= 1
right.reverse()
for i in range(len(left)):
    if left[i] == right[i]:
        print(left[i] + 1)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
N,K,C = LI()
S = input()
dp = [0 for _ in range(N)]
j = 0
last = -INF
for i in range(N):
    if S[i] == 'o':
        if i - last > C:
            j += 1
            last = i
        dp[i] = j

if j != K:
    exit(0)

last = INF

j = K+1
for i in range(N-1,-1,-1):
    if 0 < dp[i] < j :
        if last - i <= C:
            dp[i] = 0
        else:
            j = dp[i]
            last = i

last = -1
cnt = 0
for i in range(N):
    if dp[i] > 0:
        if dp[i] != last:
            if cnt == 1:
                print (last_i + 1)
            cnt = 0
            last = dp[i]
            last_i = i
        cnt += 1
if cnt == 1: print (last_i + 1)

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N,K,C = isRaw()
    S = sRaw()
    ans = []
    lefts = []
    ava = 0
    idx = 0
    while idx < N:
        if S[idx]=="x":
            idx+=1
            continue
        ava+=1
        lefts.append(idx)
        if ava==K:
            break
        idx+=C+1
    rights = []
    ava = 0
    idx = N-1
    while idx >= 0:
        if S[idx]=="x":
            idx-=1
            continue
        ava +=1
        rights.append(idx)
        if ava == K:
            break
        idx-=C+1
    ans = [str(lefts[idx]+1) for idx in range(ava) if lefts[idx] == rights[ava-1-idx]]
    return "\n".join(ans)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, C = MAP()

S = input()

L = [0]*K

cnt = 0
idx = 0
while idx <= N-1 and cnt <= K-1:
	if S[idx] != "x":
		L[cnt] = idx+1
		idx += C+1
		cnt += 1
	else:
		idx += 1

R = [0]*K
S = S[::-1]

cnt = 0
idx = 0
while idx <= N-1 and cnt <= K-1:
	if S[idx] != "x":
		R[cnt] = N-idx
		idx += C+1
		cnt += 1
	else:
		idx += 1
R = R[::-1]
for x, y in zip(L, R):
	if x == y:
		print(x)

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
dl, pl, dr, pr = [], -(C + 1), [], -(C + 1)

for i in range(N):
    if S[i] == 'o' and i - pl > C and len(dl) < K:
        dl.append(i + 1)
        pl = i
    if S[N - i - 1] == 'o' and i - pr > C and len(dr) < K:
        dr.append(N - i)
        pr = i
for i in range(K):
    if dl[i] == dr[K - i - 1]:
        print(dl[i])

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N,K,C = map(int,input().split())
    s = input()
    wf,wb = [],[]
    
    now = -10**10
    for i,st in enumerate(s):
        if st == "o" and i+1 > now+C:
            wf.append(i+1)
            now = i+1
            
    now = 10**10
    s = s[::-1]
    for i,st in enumerate(s):
        if st == "o" and N-i < now-C:
            wb.append(N-i)
            now = N-i
            
    wf = wf[:K]
    wb = wb[:K]
    for f,b in zip(wf,wb[::-1]):
        if f == b:
            print(f)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
L = [0] *K
R = [0] *K
i = 0
cnt = 0
while K > cnt:
    if S[i] == 'o':
        L[cnt] = i
        cnt += 1
        i += C
    i += 1
i = N-1
cnt = K-1
while cnt >= 0:
    if S[i] == 'o':
        R[cnt] = i
        cnt -= 1
        i -= C
    i -= 1
ans = []
for i in range(K):
    if L[i] == R[i]:
        ans.append(L[i]+1)
for x in ans:
    print(x)

Submission status: Accepted

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

r = []
l = []
i = 0
while 1:
    if S[i] == "x":
        i += 1
        continue
    r.append(i)
    if len(r) >= K:
        break
    i += C + 1

i = N - 1
while 1:
    if S[i] == "x":
        i -= 1
        continue
    l.append(i)
    if len(l) >= K:
        break
    i -= (C + 1)
for a, b in zip(r, reversed(l)):
    if a == b:
        print(a + 1)

Submission status: Accepted

Solution code:
def ris():
    return map(int, input().split())

def rs():
    return input()

n, k, c = ris()
s = rs()

i=0
rk = k
l1=[]
while(rk):
    if s[i]=='o':
        l1.append(i)
        rk-=1
        i+=c
    i+=1

i=n-1
rk=k
l2=[]
while(rk):
    if s[i]=='o':
        l2.append(i)
        rk-=1
        i-=c
    i-=1

for i1,i2 in zip(l1,reversed(l2)):
    if i1==i2:
        print(i1+1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
idx = 0
forward = []
while idx < len(s) and len(forward) < k:
    if s[idx] == 'o':
        forward.append(idx)
        idx += c + 1
    else:
        idx += 1

idx = len(s) - 1
backward = []
while idx >= 0 and len(backward) < k:
    if s[idx] == 'o':
        backward.append(idx)
        idx -= c + 1
    else:
        idx -= 1

for f, b in zip(forward, backward[::-1]):
    if f == b:
        print(f + 1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K,C = LI()
S = str(input())

L = []
R = []

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

for i in range(N)[::-1]:
    if S[i] == 'o':
        if len(R) == 0:
            R.append(i)
        else:
            if R[-1]-C-1 >= i:
                R.append(i)
    if len(R) == K:
        break

R = list(reversed(R))

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

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
X=[0]*N
Y=[0]*N
i=0
c=0
while(i<N):
    if S[i]=="o":
        c+=1
        X[i]=1
        i += (C+1)
    else:
        i+=1
if c>K:
    exit()
i = N - 1
while(i>=0):
    if S[i]=="o":
        Y[i]=1
        i -= (C+1)
    else:
        i -= 1
for i in range(N):
    if X[i] and Y[i]:
        print(i+1)

Submission status: Accepted

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

L, R = [], []

i, yasumi = 0, 0
while len(L) < K:
    if S[i] == 'o' and yasumi <= 0:
        L.append(i)
        yasumi = C + 1
    i += 1
    yasumi -= 1

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k,c=MI()
    s=SI()
    ll=[0]*n
    rr=[0]*n
    for i,m in enumerate(s):
        if m == "o":
            if i-c-1>=0:ll[i] = ll[i - c - 1] + 1
            else:ll[i]=1
        else:ll[i]=ll[i-1]
    #print(ll)
    for i in range(n-1,-1,-1):
        m=s[i]
        if m == "o":
            if i + c + 1 < n:rr[i]=rr[i+c+1]+1
            else:rr[i]=1
        else:rr[i]=rr[(i+1)%n]
    #print(rr)
    ans=[]
    if n==1:ans.append(1)
    if n>1 and rr[1]<k:ans.append(1)
    for i in range(1,n-1):
        if ll[i-1]+rr[i+1]<k:ans.append(i+1)
    if n>1 and ll[n-2]<k:ans.append(n)
    print(*ans,sep="\n")

main()

Submission status: Accepted

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

L = list()
R = list()


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

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

R.reverse()

# print(L)
# print(R)
length = min(len(L), len(R))
for i in range(length):
    if L[i] == R[i]:
        print(L[i] + 1)

Submission status: Accepted

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

A = list()
B = list()

i = 0
num = 0
while num < K:
  if S[i] == "o":
    A.append(i)
    num += 1
    i += C
  i += 1
i = len(S)-1
num = 0
while num < K:
  if S[i] == "o":
    B.append(i)
    num+=1
    i -= C
  i -= 1
B.sort()

for i,j in zip(A,B):
  if i == j:
    print(i+1)

Submission status: Accepted

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

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

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

    # print(L)
    # print(R)

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

Submission status: Accepted

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

DP1 = []
DP2 = []

day = 0
work = 0
while day < n and work < k:
    if S[day] == 'o':
        DP1.append(day)
        day += c + 1
        work += 1

    else:
        day += 1

day = n-1
work = 0
while day >= 0 and work < k:
    if S[day] == 'o':
        DP2.append(day)
        day -= c + 1
        work += 1
    else:
        day -= 1

for day1, day2 in zip(DP1, DP2[::-1]):
    if day1 == day2:
        print(day1+1)

Submission status: Accepted

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

# 前後
i = 0
l1 = []
while i <= n-1:
    if s[i] == 'o':
        l1.append(i+1)
        i += c + 1
    else:
        i += 1
    if len(l1) >= k:
        break
i = n-1
l2 = []
while i >= 0:
    if s[i] == 'o':
        l2.append(i+1)
        i -= (c + 1)
    else:
        i -= 1
    if len(l2) >= k:
        break
ans = []
for i, j in zip(l1, l2[::-1]):
    if i == j:
        ans.append(i)
print("\n".join(list(map(str, ans))))

Submission status: Accepted

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

N,K,C = map(int,input().split())
S = input()
#%%
assign_t = [False]*N
assign_b = [False]*N


i = 0
num = 0
while i<N:
    if S[i]=='o':
        assign_t[i]=True
        num += 1
        i += C+1
    else:
        i += 1

if num>K:
    print()
    sys.exit()

i = N-1
num = 0
while i>=0 and num<K:
    if S[i]=='o':
        assign_b[i]=True
        num += 1
        i -= C+1
    else:
        i -=1


for i in range(N):
    if assign_t[i] and assign_b[i]:
        print(i+1)

Submission status: Accepted

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

b = []

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.append(n+d)
    d -= c+1

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    if d == b[-i-1]:
        print(d+1)
    d += c+1

Submission status: Accepted

Solution code:
N,K,C =map(int,input().rstrip().split(" "))
S = input()
kinmu = 0
niti = 0
f = []
b = []
kinmu = 0
niti = 0
while kinmu < K and niti < N:
  if S[niti] == "o":
    f.append(niti)
    kinmu += 1
    niti += C
  niti += 1
kinmu = 0
niti = N -1
while kinmu < K and niti >= 0:
  if S[niti] == "o":
    b.append(niti)
    kinmu += 1
    niti -= C
  niti -= 1
b.reverse()
for i in range(K):
  if f[i] == b[i]:
    print(f[i] + 1)

Submission status: Accepted

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

# 前貪欲
ansl = []
before = -float("inf")
for idx,s in enumerate(sl):
    if s == "o" and before + c < idx:
        before = idx
        ansl.append(idx)

# 後貪欲
ansl2 = []
before = -float("inf")
for idx,s in enumerate(sl[::-1]):
    if s == "o" and before + c < idx:
        before = idx
        ansl2.append(n-idx-1)


for a1,a2 in zip(ansl[:k], ansl2[:k][::-1]):
    if a1 == a2:
        print(a1+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetReverse():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[::-1]):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(len(S) - 1 - i)
        last = i
    return reversed(ret)


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    reverse_ans = GetReverse()

    return sorted(list(set(base_ans) & set(reverse_ans)))


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a + 1)

Submission status: Accepted

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

wc = 0
arr = ["x"] * N
arr2 = ["x"] * N
cur = 0

while cur < N:
    if S[cur] == "x":
        cur += 1
        continue
    wc += 1
    arr[cur] = wc
    cur += C + 1

cur = N - 1
wc = K + 1
while cur >= 0:
    if S[cur] == "x":
        cur -= 1
        continue
    wc -= 1
    arr2[cur] = wc
    cur -= C + 1

for i, (a, b) in enumerate(zip(arr, arr2)):
    if a == b and a != "x":
        print(i + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

last = deque()
pre = -C - 1
for i, s in enumerate(reversed(S)):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break

count = 0
pre = -C - 1
x = last.popleft()
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    count += 1
    while x < i:
      x = last.popleft()
    if x == i and count + len(last) == K:
      print(i + 1)
    pre = i
    if count == K:
      break

Submission status: Accepted

Solution code:
def main():
    n,k,c=map(int,input().split())
    S=input()
    l1=[[0,0] for _ in range(n)]
    l2=[0]*n
    memo=[0]*n
    x=0
    for i in range(n):
        if S[i]=="o" and memo[i]==0:
            x+=1
            l1[i][0]=x
            l1[i][1]=i+c+1
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        elif S[i]=="o" and memo[i]==1:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
        elif S[i]=="x" and memo[i]==0:
            l1[i][0]=x
            l1[i][1]=i+1
        else:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
    S_=S[::-1]
    memo=[0]*n
    x=0
    for i in range(n):
        if S_[i]=="o" and memo[i]==0:
            x+=1
            l2[i]=x
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        else:
            l2[i]=x
    l2=l2[::-1]
    ans=0
    for i in range(n):
        if S[i]=="o":
            x=0
            if i!=0:
                x+=l1[i-1][0]
            if i==0 and n!=1:
                x+=l2[1]
            else:
                if l1[i-1][1]<n and i<n-1:
                    x+=l2[max(l1[i-1][1],i+1)]
            if x<k:
                print(i+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

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)
if len(cand)==k:
  for val in cand:
    print(val+1)
else:
  cnt1=[0]*n
  cnt2=[0]*n
  prev=0
  cnt=0
  for i in range(l):
    if s[i]=='o' and i>=prev:
      cnt+=1
      cnt1[i]=cnt
      prev=i+(c+1)
    else:
      cnt1[i]=cnt
  prev=l-1
  cnt=0
  for i in range(l-1,-1,-1):
    if s[i]=='o' and i<=prev:
      cnt+=1
      cnt2[i]=cnt
      prev=i-(c+1)
    else:
      cnt2[i]=cnt
  ans=[]
  for i in range(len(cand)):
    if i==0:
      if cnt2[cand[i]+1]<k:
        ans.append(cand[i]+1)
    elif i==len(cand)-1:
      if cnt1[cand[i]-1]<k:
        ans.append(cand[i]+1)
    else:
      if cnt1[cand[i]-1]+cnt2[cand[i]+1]<k:
        ans.append(cand[i]+1)
  for val in ans:
    print(val)