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

    i = 0
    c = 0
    p = [-1] * N
    while c < K:
        if S[i] == 'o':
            p[i] = c
            c += 1
            i += C
        i += 1

    i = N - 1
    c = K - 1
    q = [-1] * N
    while c >= 0:
        if S[i] == 'o':
            q[i] = c
            c -= 1
            i -= C
        i -= 1

    for i in range(N):
        if ~p[i] and p[i] == q[i]:
            print(i + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K, C = list(map(int, input().split(' ')))
    S = input()
    R, L = [0 for _ in range(K)], [0 for _ in range(K)]
    # calc first dates
    index, cnt = 0, 0
    while cnt < K and index <= N - 1:
        if S[index] == 'o':
            R[cnt] = index
            index += C + 1
            cnt += 1
        else:
            index += 1
    # calc last dates
    S = S[::-1]
    index, cnt = 0, 0
    while cnt < K and index <= N - 1:
        if S[index] == 'o':
            L[K - 1 - cnt] = N - 1 - index
            index += C + 1
            cnt += 1
        else:
            index += 1
    ans = [R[k] + 1 for k in range(K) if R[k] == L[k]]
    if len(ans) == 0:
        print('')
    else:
        for a in ans:
            print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
#n日中k日働く。働いたらc日働かない

s=list(input())

#Xの時、i日後には働かない

ll=[]
rr=[]

day=0
while day<n:
    if s[day]=="o":
        ll.append(day)
        day+=(c+1)
    else:
        day+=1
    if len(ll)>=k:
        break

day=n-1
while 0<=day:
    if s[day]=="o":
        rr.append(day)
        day-=(c+1)
    else:
        day-=1
    if len(rr)>=k:
        break
        
rr=rr[::-1]
#print(ll)
#print(rr)

for i in range(k):
    if ll[i]==rr[i]:
        print(ll[i]+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

    Left=deque([])
    Right=deque([])

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

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.appendleft(counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        l=Left.popleft()
        r=Right.popleft()
        if l==r:
            print(l+1)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n, k, c = map(int, input().split())
s = input()
left = [-1]*k
right = [-1]*k

d = w = 0
while w < k:
    if s[d] == "o":
        left[w] = d
        w += 1
        d += c+1
    else:
        d += 1

d, w = n-1, k-1
while w >= 0:
    if s[d] == "o":
        right[w] = d
        w -= 1
        d -= c+1
    else:
        d -= 1

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

Submission status: Accepted

Solution code:
# E - Yutori
N,K,C = map(int,input().split())
S = input()
L = [0]*K
R = [0]*K

i = 0
for j in range(K):
    while S[i]!='o':
        i += 1
    L[j] = i
    i += C+1

i = N-1
for j in range(K-1,-1,-1):
    while S[i]!='o':
        i -= 1
    R[j] = i
    i -= C+1
    
for j in range(K):
    if L[j]==R[j]:
        print(L[j]+1)

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
day=[]
for i in range(len(S)):
  if S[i]=='o':
    day.append(i+1)
E=[day[0]]    
cur=day[0]
for i in range(1,len(day)):
  if day[i]>=cur+C+1:
    cur=day[i]
    E.append(cur)
F=[day[len(day)-1]]
cur=day[len(day)-1]
for i in range(len(day)-1,-1,-1):
  if day[i]<=cur-C-1:
    cur=day[i]
    F.append(cur)
if len(E)>K:
  while len(E)>K:
    E.pop()
if len(F)>K:  
  while len(F)>K:
    F.pop()
F.reverse()

for i in range(K):
  if E[i]==F[i]:
    print(E[i])

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, k, c = map(int, input().split())
    def sub(s):
        n = len(s)
        cur = 0
        last = -(c + 1)
        res = [0] * (n + 1)
        for i in range(n):
            if (i - last > c and s[i] == "o"):
                cur += 1
                last = i
            res[i + 1] = cur
        return res
    
    s = input()
    left = sub(s)
    t = s
    t = t[::-1]
    right = sub(t)
    for i in range(n):
        if s[i] == "x": continue
        if left[i] + right[n - i - 1] < k:
            print(i+1)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

i=0
counter=0
fslist=[]

while counter < k:
	if s[i] == "o":
		fslist.append(i)
		i += c+1
		counter += 1
	else:
		i += 1

i=-1
counter=0
felist=[]

while counter < k:
	if s[i] == "o":
		felist.append(i+n)
		i -= c+1
		counter += 1
	else:
		i -= 1

felist.reverse()

for i in range(k):
	if fslist[i] == felist[i]:
		print(fslist[i]+1)

Submission status: Accepted

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

l = [-1] * N
r = [-1] * N

idx = 1
i = 0
C += 1

while i < N:
    if S[i] == 'o':
        l[i] = idx
        idx += 1
        i += C
    else:
        i += 1

idx = 1
i = N-1
while 0 <= i:
    if S[i] == 'o':
        r[i] = idx
        idx += 1
        i -= C
    else:
        i -= 1

if idx-1 <= K:
    for i in range(N):
        if l[i] != -1 and r[i] != -1: print(i+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = [i == "o" for i in list(input())]
i = 0
cnt = 0
l = [0]*n
r = [0]*n
while i < n:
    if s[i]:
        cnt += 1
        for j in range(i,c+i+1):
            if j < n:
                l[j] = cnt
        i += c+1
    else:
        l[i] = cnt
        i += 1
i = n-1
cnt = 0
while i >= 0:
    if s[i]:
        cnt += 1
        for j in range(i,i-1-c,-1):
            if j >= 0:
                r[j] = cnt
        i -= c+1
    else:
        r[i] = cnt
        i -= 1
#print(l,r)
r.append(0)
if r[1] < k:
    print(1)
for i in range(1,n-1):
    if not s[i]:
        continue
    if l[i-1] + r[i+1] < k:
        print(i+1)
if l[n-2] < k:
    print(n)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k,c = LI()
    s = S()

    l = set()
    i = 0
    while i < n:
        if s[i] == 'x':
            i += 1
        else:
            l.add(i+1)
            i += c + 1

    if len(l) > k:
        return ""

    r = set()
    i = n - 1
    while i >= 0:
        if s[i] == 'x':
            i -= 1
        else:
            r.add(i+1)
            i -= c + 1

    return JA(sorted(l & r), "\n")

print(main())

Submission status: Accepted

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

    L = [-1] * K  # 0-ind

    i = 0
    cur = 0
    while i < N:
        if S[i] == 'o':
            L[cur] = i
            cur += 1
            if cur == K: break
            i += C
        i += 1

    R = [-1] * K  # 0-ind

    i = N - 1
    cur = K - 1
    while i >= 0:
        if S[i] == 'o':
            R[cur] = i
            cur -= 1
            if cur == -1: break
            i -= C
        i -= 1

    ans = (l + 1 for l, r in zip(L, R) if l == r)  # 1-ind
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
l=list();r=list()
nex=0
for i in range(n):
	if i<nex:
		continue
	if s[i]=="o":
		nex=i+c+1
		l.append(i)
		if len(l)==k:
			break
nex=-1
for i in range(n):
	if i<nex:
		continue
	if s[-i-1]=="o":
		nex=i+c+1
		r.append(n-i-1)
		if len(r)==k:
			break
r=r[::-1]
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()

s2 = s[::-1]

dp1 = [0] * (n + 2)
dp2 = [0] * (n + 2)

for (dp, ss) in zip([dp1, dp2], [s, s2]):
    for i in range(n):
        if ss[i] == 'x':
            dp[i+1] = dp[i]
        elif i <= c:
            dp[i+1] = min(1, dp[i] + 1)
        else:
            dp[i+1] = max(dp[i-c] + 1, dp[i])

dp2 = dp2[::-1]

for i in range(1, n+1):
    if s[i-1] == 'o' and dp1[i-1] + dp2[i+1] < k:
        print(i)

Submission status: Accepted

Solution code:
# 解説を参考に作成


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

    left = []
    rest = 0
    work = 0
    for i in range(N):
        if S[i] == 'o' and rest == 0:
            left.append(i)
            rest = C + 1
            work += 1
        if rest > 0:
            rest -= 1
        if work == K:
            break

    right = []
    rest = 0
    work = 0
    for i in reversed(range(N)):
        if S[i] == 'o' and rest == 0:
            right.append(i)
            rest = C + 1
            work += 1
        if rest > 0:
            rest -= 1
        if work == K:
            break
    right = list(reversed(right))

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

mae = [-1] * N
i = 0
count = 0
while i < N and count < K:
    if S[i] == 'o':
        mae[i] = count
        count += 1
        i += C + 1
    else:
        i += 1

ushiro = [-1] * N
i = N - 1
count = 0
while i >= 0 and count < K:
    if S[i] == 'o':
        ushiro[i] = K - count - 1
        count += 1
        i -= (C + 1)
    else:
        i -= 1

for i in range(N):
    if mae[i] == ushiro[i] and mae[i] != -1:
        print (i + 1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
fastest_schedule = [None for i in range(n)]
latest_schedule = [None for i in range(n)]
count = 1
last_workday = -10**10
for i in range(n):
    if s[i] == 'o' and i - last_workday > c:
        fastest_schedule[i] = count
        last_workday = i
        if count < k:
            count += 1
        else:
            break
count = k
last_workday = 10**18
for i in range(n-1,-1,-1):
    if s[i] == 'o' and last_workday - i > c:
        latest_schedule[i] = count
        last_workday = i
        if count > 1:
            count -= 1
        else:
            break

for i in range(n):
    if fastest_schedule[i] == latest_schedule[i] and fastest_schedule[i] != None:
        print(i+1)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = input()
cnt = 0
e = 0
l = []
for i,si in enumerate(s):
  if e == k:
    break
  if cnt > 0:
    cnt -= 1
    continue
  if si == 'o':
    l.append(i+1)
    cnt = c
    e += 1
  
r = []
cnt = 0
d = 0
for i,si in enumerate(s[::-1]):
  if d == k:
    break
  if cnt > 0:
    cnt -= 1
    continue
  if si == 'o':
    r.append(n-i)
    cnt = c
    d += 1
    
for i in range(k):
  if l[i] == r[k-1-i]:
    print(l[i])

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, K, C = nm()
S = ns()
assert len(S) == N

INF = 1 << 60


def solve():
    lfilled = [0] * N  # max left count where i-th position is filled
    lempty = [0] * N  # max left count where i-th position is empty
    for i in range(0, N):
        if i > 0:
            lempty[i] = max(lempty[i - 1], lfilled[i - 1])
        if S[i] == "x":
            lfilled[i] = -INF
        elif i - C >= 0:
            lfilled[i] = lempty[i - C] + 1
        else:
            lfilled[i] = 1

    rfilled = [0] * N
    rempty = [0] * N
    for i in range(N - 1, -1, -1):
        if i < N - 1:
            rempty[i] = max(rempty[i + 1], rfilled[i + 1])
        if S[i] == "x":
            rfilled[i] = -INF
        elif i + C < N:
            rfilled[i] = rempty[i + C] + 1
        else:
            rfilled[i] = 1

    def must_work(s, t):
        l = max(lfilled[s - 1], lempty[s - 1]) if s - 1 >= 0 else 0
        r = max(rfilled[t], rempty[t]) if t < N else 0
        # print(f"day {s}-{t}: l+r={l+r} l={l} r={r}", file=sys.stderr)
        return l + r < K

    # imos
    no_need_to_work = [0] * (N + C)
    for t in range(1, N + C):
        s = max(t - C, 0)
        if not must_work(s, t):
            no_need_to_work[s] += 1
            no_need_to_work[t] -= 1
    acc = [0] * (N + C + 1)
    ans = []
    for i in range(1, N + 1):
        acc[i] += acc[i - 1] + no_need_to_work[i - 1]
        if acc[i] == 0:
            ans.append(i)
    return ans


def solve0():
    workable = [i + 1 for i, x in enumerate(S) if x == "o"]
    if len(workable) == K:
        return workable
    assert len(workable) > K
    return []


if C == 0:
    print(*solve0(), sep="\n")
else:
    print(*solve(), sep="\n")

Submission status: Accepted

Solution code:
from sys import stdin, stdout

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



vec = []
rvec = []

i = 0
while i < N:
    if S[i] == 'o':
        vec.append(i)
        i += C
    i += 1

j = N - 1
while j >= 0:
    if S[j] == 'o':
        rvec.append(j)
        j -= C
    j -= 1


ans = []
for i in range(K):
    if vec[i] == rvec[K - i - 1]:
        stdout.write(str(vec[i] + 1) + '\n')
stdout.write('\n')

Submission status: Accepted

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

L = []
R = []

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K, C = lr()
S = sr()
# 左からと右からでそれぞれ貪欲、重なったところが必須
left = []; right = []

def work(S):
    ret = []
    cur = 0
    count = 0
    while count < K:
        if S[cur] == 'o':
            count += 1
            ret.append(cur)
            cur += C + 1
        else:
            cur += 1
    return ret

left = work(S)
right = work(S[::-1])
right = [N-1-x for x in right]
right.reverse()
answer = []
for l, r in zip(left, right):
    if l == r:
        answer.append(str(l+1))
print('\n'.join(answer))

Submission status: Accepted

Solution code:
from collections import deque
import copy

N, K, C = map(int,input().split())
S = input().split()[0]
TW = 0
q = []

for s in range(len(S)):
    if S[s] == 'o':
        q.append(s+1)

WD = []
LD = 0

for s in q:
    if len(WD) > K:
        break
    if LD == 0:
        WD.append(s)
        LD = s
    elif s-LD <= C:
        continue
    else:
        WD.append(s)
        LD = s


WDR = []
LD = 0
q.reverse()

for s in q:
    if len(WDR) > K:
        break
    if LD == 0:
        WDR.append(s)
        LD = s
    elif LD - s <= C:
        continue
    else:
        WDR.append(s)
        LD = s


for d in range(len(WD)):
    if WD[d] == WDR[len(WD)-d-1]:
        print(WD[d])

Submission status: Accepted

Solution code:
N, K, C = [int(_) for _ in input().split()]
S = input()
cand = [i + 1 for i, s in enumerate(S) if s == 'o']
F = [[cand[0]]]
for c in cand[1:]:
    if c - F[-1][0] > C:
        F += [[]]
    F[-1] += [c]
if len(F) > K:
    exit()
B = [[cand[-1]]]
for c in cand[-2::-1]:
    if B[-1][0] - c > C:
        B[-1] = B[-1][::-1]
        B += [[]]
    B[-1] += [c]
B = B[::-1]
B[0] = B[0][::-1]
ans = []
for f, b in zip(F, B):
    if len(f) == 1 or f[1] not in b:
        ans += [f[0]]
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
INF=10**18
N,K,C=map(int,input().split())
S=input()
left=[0]*N
right=[0]*N
l=-INF
for i in range(N):
    if S[i]=='o':
        if l==-INF:
            left[i]=1
            l=i+C
        elif l<i:
            left[i]=max(left[i],left[i-C-1]+1)
            l=i+C
        else:
            left[i]=left[i-1]
    else:
        left[i]=left[i-1]
r=INF
for i in reversed(range(N)):
    if S[i]=='o':
        if r==INF:
            right[i]=1
            r=i
        elif i<r-C:
            right[i]=max(right[i],right[i+C+1]+1)
            r=i
        else:
            right[i]=right[(i+1)%N]
    else:
        right[i]=right[(i+1)%N]

for i in range(N):
    lsum=left[i-1] if i-1>=0 else 0
    rsum=right[i+1] if i+1<N else 0
    if lsum+rsum<K:
        print(i+1)

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools
# いくつか入力
n, k, c = (int(i) for i in input().split())  

# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
m = list(input())

l=[-1]*n
r=[-1]*n

a=0
b=c
for i in range(n):
    if b>=c and m[i]=='o':
        b=0
        l[a]=i
        a += 1
    else:
        b += 1
    if a == k:
        break
a=k-1
b=c
for i in range(n-1,-1,-1):
    if b>=c and m[i]=='o':
        b=0
        r[a]=i
        a -= 1
    else:
        b += 1
    if a == k:
        break



answer=0
for i in range(n):
    if l[i] == r[i] and l[i]>=0:
        print(l[i]+1)

Submission status: Accepted

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

l = [0] * k
r = [0] * k
l_idx = 0
r_idx = k - 1
l_cnt = r_cnt = 0
for i in range(n):
    if s[i] == "o" and (l_cnt >= c or l_idx == 0) and l_idx < k:
        l[l_idx] = i
        l_cnt = -1
        l_idx += 1
    if s[n-i-1] == "o" and (r_cnt >= c or r_idx == k - 1) and r_idx >= 0:
        r[r_idx] = n - i - 1
        r_cnt = -1
        r_idx -= 1
    l_cnt += 1
    r_cnt += 1

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 = list(input())

l = [0] * N
r = [0] * N
cnt = 1
yutori = 10 ** 10
for i, s in enumerate(S):
    if s == "o" and yutori > C:
        l[i] = cnt
        yutori = 0
        cnt += 1
    yutori += 1

S.reverse()
yutori = 10 ** 10
cnt = K
for i, s in enumerate(S):
    if s == "o" and yutori > C:
        r[i] = cnt
        yutori = 0
        cnt -= 1
    yutori += 1

ans = set()
r.reverse()
for i in range(N):
    if l[i] == r[i] and l[i] > 0:
        ans.add(i+1)

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

Submission status: Accepted

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

l = []
r = []

i = 0
j = N-1

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

while j >= 0 and len(r) < K:
    if S[j] == 'o':
        r.append(j)
        j -= C
    j -= 1

r.reverse()

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()
dp0 = [0]*K
dp1 = [0]*K
step = C
cnt = 0
for i in range(N):
  if step>=C and S[i]=='o':
    dp0[cnt] = i
    cnt += 1
    if cnt==K:
      break
    step = 0
  else:
    step += 1
step = C
cnt = K-1
for i in range(N-1,-1,-1):
  if step>=C and S[i]=='o':
    dp1[cnt] = i
    cnt -= 1
    if cnt==-1:
      break
    step = 0
  else:
    step += 1
ans = 0
for i,(a,b) in enumerate(zip(dp0,dp1)):
  if a==b:
    print(a+1)

Submission status: Accepted

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

left = []
i = 0
while len(left) < k:
  if s[i] == 'o':
    left.append(i)
    i += c + 1
  else:
    i += 1

right = []
i = n - 1
while len(right) < k:
  if s[i] == 'o':
    right.append(i)
    i -= c + 1
  else:
    i -= 1

right = right[::-1]

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

Submission status: Accepted

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:
  if c == K:
    break
  if S[i]=="o":
    R.append(i)
    c += 1
    i -= C+1
  else:
    i -= 1

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

Submission status: Accepted

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

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