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:
n, k, c = map(int, input().split())
s = input()

def getPositions():
    res = []
    i = 0
    while i < n:
        if s[i] == 'o':
            res.append(i)
            i += c + 1
        else:
            i += 1
    return res

l = getPositions()

s = s[::-1]
r = getPositions()
for i in range(k):
    r[i] = n-1-r[i]
s = s[::-1]

lastL = [-1]*(n+1)
for i in range(k):
    lastL[l[i]+1] = i

for i in range(n):
    if lastL[i+1] == -1:
        lastL[i+1] = lastL[i]

lastR = [-1] * (n+1)
for i in range(k):
    lastR[r[i]] = i
for i in range(n-1, -1, -1):
    if lastR[i] == -1:
        lastR[i] = lastR[i+1]

for i in range(n):
    if s[i] == 'x': continue
    li = lastL[i]
    ri = lastR[i+1]

    cnt = 0
    if li != -1: cnt += li+1
    if ri != -1: cnt += ri+1
    if (li != -1) and (ri != -1) and (r[ri]-l[li] <= c): cnt -= 1
    if cnt >= k: continue
    print(i+1)

Submission status: Accepted

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

cand=[]
for i in range(n):
    if s[i]=="o":
        cand.append(i)

left=[0]*n
prev=0
cnt=0

for i in range(n):
    if s[i]=="o" and i>=prev:
        cnt+=1
        left[i]=cnt
        prev=i+c+1
    else:
        left[i]=cnt

right=[0]*n
prev=n-1
cnt=0

for i in range(n-1,-1,-1):
    if s[i]=="o" and i<=prev:
        cnt+=1
        right[i]=cnt
        prev=i-c-1
    else:
        right[i]=cnt

for i in ([left,right]):
    i.insert(0,0)
    i.append(0)

ans=[]

for i in range(1,n+1):
    a=left[i-1]+right[i+1]
    if a<k:
        ans.append(i)
    
for j in ans:
    print(j)

Submission status: Accepted

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

bound_to_work = [0] * n

def get_days(s):
    days = [0] * n
    changes = [0] * n
    last_day = -1
    ndays = 0
    for i in range(n):
        if (last_day == -1 or i - last_day > c) and s[i] == 'o':
            ndays += 1
            last_day = i
            changes[i] = 1
        days[i] = ndays
    return days

ldays = get_days(s)
rdays = get_days(s[::-1])[::-1]


for i in range(n):
    lchanges = (i > 0 and ldays[i] != ldays[i - 1] or i == 0)
    rchanges = i == n - 1 or rdays[i + 1] != rdays[i]
    if  lchanges and rchanges and ldays[i] + rdays[i] == k + 1:
        bound_to_work[i] = 1

for i, f in enumerate(bound_to_work):
    if f:
        print(i + 1)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split());s=input();
l=[];r=[];i=0;j=n-1
while 0<=i<=n-1:
  if s[i]=="o":l+=i,;i+=c+1
  else:i+=1
while 0<=j<=n-1:
  if s[j]=="o":r+=j,;j-=c+1
  else:j-=1
a=list(set(l)&set(r))
if len(a)>k:exit()
for q in sorted(a):print(q+1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
L = [-1]*k
R = [-1]*k
now = 0
cnt = 0
while now < n and cnt < k:
  if s[now] == "o":
    L[cnt] = now
    cnt += 1
    now += c+1
  else:
    now += 1
now = n-1
cnt = k-1
while now >= 0 and cnt >= 0:
  if s[now] == "o":
    R[cnt] = now
    cnt -= 1
    now -= c+1
  else:
    now -= 1
A = []
for i in range(k):
  if L[i] == R[i]:
    A.append(L[i]+1)
print(*A, sep="\n")

Submission status: Accepted

Solution code:
INF = float("inf")
n, k, c = map(int, input().split())
s = input()
l, r = [(0, -INF)] + [None] * n, [(0, INF)] + [None] * n
for i, x in enumerate(s):
    wn, wd = l[i]
    l[i+1] = (wn+1, i) if x == "o" and i-wd > c else l[i]

for i, x in enumerate(s[::-1]):
    wn, wd = r[i]
    j = n-i-1
    r[i+1] = (wn+1, j) if x == "o" and wd-j > c else r[i]

for i in range(n):
    ln, ld = l[i]
    rn, rd = r[n-i-1]
    w = ln + rn
    if rd - ld <= c: w -= 1
    if w < k: print(i+1)

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K, C = MAP()
S = input()

L = [0] * K
cur = 0
idx = 0
while idx < K:
    if S[cur] == 'o':
        L[idx] = cur
        idx += 1
        cur += C + 1
    else:
        cur += 1
R = [0] * K
cur = N - 1
idx = K - 1
while idx >= 0:
    if S[cur] == 'o':
        R[idx] = cur
        idx -= 1
        cur -= C + 1
    else:
        cur -= 1

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

Submission status: Accepted

Solution code:
def e_yutori():
    # 参考: https://drken1215.hatenablog.com/entry/2020/04/05/163400
    N, K, C = [int(i) for i in input().split()]
    S = input()

    def sub_solver(string):
        """string が表す労働日時に対して、労働数が最大になるように働いたとき、
        i 日目には何回働いているかのリストを返す"""
        n = len(string)
        current, last = 0, -C - 1  # 最初に 'o' があっても動作するように設定
        ret = [0] * (n + 1)

        for i in range(n):
            if i - last > C and string[i] == 'o':
                current += 1
                last = i
            ret[i + 1] = current
        return ret

    left = sub_solver(S)
    right = sub_solver(S[::-1])
    ans = []
    for i in range(N):
        if S[i] == 'x':
            continue
        if left[i] + right[N - i - 1] < K:
            ans.append(i + 1)
    return '\n'.join(map(str, ans))

print(e_yutori())

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
l=[0]*k
r=[0]*k
ld=0
rd=n-1
for i in range(k):
    j=k-1-i
    while s[ld]=='x':
        ld+=1
    while s[rd]=='x':
        rd-=1
    l[i]=ld
    ld+=1+c
    r[j]=rd
    rd-=1+c
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 = str(input())
works1 = 0
works2 = 0
l1 = []
l2 = []
i = 0
while i < N and works1 < K:
  if S[i] == "o":
    l1.append(i+1)
    i = i+C+1
    works1 += 1
  else:
    i = i+1
i = N-1
while i > -1 and works2 < K:
    if S[i] == "o":
      l2.append(i+1)
      i = i-C-1
      works2 = works2+1
    else:
      i = i-1

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

Submission status: Accepted

Solution code:
n,k,c = map(int, input().split())
s = input()
L = []
L.append(-c)
workday = 1
for i in range(1, n+1):
    if i <= L[workday-1] + c:
        continue
    if s[i-1] == 'x':
        continue
    L.append(i)
    workday += 1
    if workday == k + 1:
        break
R = [0] * (k+2)
R[k+1] = n + c + 1
workday = k
for i in range(n, 0, -1):
    if i >= R[workday+1] - c:
        continue
    if s[i-1] == 'x':
        continue
    R[workday] = i
    workday -= 1
    if workday == 0:
        break
for i in range(1, k+1):
    if L[i] == R[i]:
        print(L[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr  5 22:11:18 2020

@author: Kanaru Sato
"""

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

early = []
late = []

i = 0
count = 0
while i < n and count < k:
    if s[i] == "o":
        early.append(i)
        i = i+c+1
        count = count+1
    else:
        i = i+1


i = n-1
count = 0
while i > -1 and count < k:
    if s[i] == "o":
        late.append(i)
        i = i-c-1
        count = count+1
    else:
        i = i-1

for i in range(len(early)):
    if early[i] == late[k-i-1]:
        print(early[i]+1)

Submission status: Accepted

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

rest = 0
for i, c in enumerate(S):
    if rest > 0:
        rest -= 1
        continue

    if c == 'o':
        rest = C
        work_day_front.append(i)
max_work = len(work_day_front)

rest = 0
for i, c in enumerate(S[::-1]):
    if rest > 0:
        rest -= 1
        continue
    if c == 'o':
        rest = C
        work_day_back.append(N-i-1)

work_day_back = work_day_back[::-1]


if len(work_day_front) > K:
    print()
    exit()

ans = []
for i in range(len(work_day_back)):
    if work_day_back[i] == work_day_front[i]:
        ans.append(str(work_day_back[i]+1))
print("\n".join(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = str(input())
A = [0] * K
B = [0] * K
a = 0
b = N - 1
for i in range(K):
    j = K - 1 - i
    while S[a] == 'x':
        a += 1
    while S[b] == 'x':
        b -= 1
    A[i] = a
    a += 1 + C
    B[j] = b
    b -= 1 + C
for i in range(K):
    if A[i] == B[i]:
        print(A[i] + 1)

Submission status: Accepted

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

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

def checkend(S0):
    count=0
    index=N-1
    out=[0]*K
    while count<K and index>=0:
        if S0[index]=='o':
            out[K-1-count]=index
            count+=1
            index-=(C+1)
        else:
            index-=1
    if count==K:
        return 1,out
    return 0,out



flag0,out0=check0(S)
flagend,outend=checkend(S)
if flag0==1:
    for i in range(K):
        if out0[i]==outend[i]:
            print(out0[i]+1)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=list(input())
for i in range(len(s)):
	if s[i]=="o":
		s[i]=True
	else:
		s[i]=False
i=0
work1=[]
while len(work1)<k:
	if s[i]:
		work1.append(i)
		i+=c+1
	else:
		i+=1
i=n-1
work2=[]
while len(work2)<k:
	if s[i]:
		work2.append(i)
		i-=c+1
	else:
		i-=1
work2.sort()
for i in range(k):
	if work1[i]==work2[i]:
		print(work1[i]+1)

Submission status: Accepted

Solution code:
N, K, C = map(int,input().split())
S = input()
workable = []
#はたらける日付を出しとく(後で使う)
for i in range(N):
    if S[i] == 'o':
        workable.append(i+1)

#print(workable)

#j-1日目までに頑張ってはたらいたときの最大値(bfore_j)
bfore_j = {1:0}

work = 0
pas = 0
work_a = []
for j in range(N-1):
    if pas == 0:
        if S[j] == 'o':
            work += 1
            pas = C
            work_a.append(j+1)
            
    else:
        pas -= 1
    bfore_j[j+2] = work

#print(bfore_j)

#j+1日目以降に頑張ってはたらいたときの最大値

after_j = {N:0}


work = 0
pas = 0
for l in range(N):
    if pas == 0:
        if S[N-1-l] == 'o':
            work += 1
            pas = C    
    else:
        pas -= 1

    after_j[N-l-1] = work

#print(after_j)

for m in workable:
    if bfore_j[m] + after_j[m] < K:
        print(m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


n, k, c = mii()
s = si()


def get_positions():
    res = []
    i = 0
    while i < n and len(res) < k:
        if s[i] == 'o':
            res.append(i)
            i += c+1
        else:
            i += 1
    return res


l = get_positions()
s = s[::-1]
r = get_positions()
for i in range(k):
    r[i] = n-1-r[i]
s = s[::-1]

lastL = [-1] * (n+1)
for i in range(k):
    lastL[l[i]+1] = i
for i in range(n):
    if lastL[i+1] == -1:
        lastL[i+1] = lastL[i]

lastR = [-1] * (n+1)
for i in range(k):
    lastR[r[i]] = i
for i in reversed(range(n)):
    if lastR[i] == -1:
        lastR[i] = lastR[i+1]


for i in range(n):
    if s[i] == 'x':
        continue
    li = lastL[i]
    ri = lastR[i+1]
    cnt = 0
    if li != -1:
        cnt += li + 1
    if ri != -1:
        cnt += ri + 1
    if li != -1 and ri != -1 and r[ri]-l[li] <= c:
        cnt -= 1
    if cnt >= k:
        continue
    print(i+1)

Submission status: Accepted

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

def getpos(s):
    l = []
    i = 0
    while i <= n-1 and len(l) < k:
        if s[i] == 'o':
            l.append(i)
            i += c+1
        else:
            i += 1
    return l

l = getpos(s)

s.reverse()
r = getpos(s)
for i in range(len(r)):
    r[i] = n-1-r[i]

#print(l)
#print(r)

lastl = [-1]*(n+1)
lastr = [-1]*(n+1)

for i in range(k):
    lastl[l[i]+1] = i

for i in range(n):
    if lastl[i+1] == -1:
        lastl[i+1] = lastl[i]

for i in range(k):
    lastr[r[i]] = i

for i in reversed(range(n)):
    if lastr[i] == -1:
        lastr[i] = lastr[i+1]

#print(lastl)
#print(lastr)

ans = []
s.reverse()
for i in range(n):
    if s[i] != 'o':
        continue
    cnt = 0
    cnt += lastl[i]+1
    cnt += lastr[i+1]+1
    if lastl[i] != -1 and lastr[i+1] != -1 and r[lastr[i+1]] - l[lastl[i]] <= c:
        cnt -= 1
    if cnt < k:
        ans.append(i+1)

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

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

l = [-c-1]
for i in range(n):
    if s[i] == 'o' and i - l[-1] > c:
        l.append(i)
r = [n + c]
for i in reversed(range(n)):
    if s[i] == 'o' and r[-1] - i > c:
        r.append(i)
r.reverse()


if len(l)-1 == k:
    for li, ri in zip(l[1:], r):
        if li == ri:
            print(li + 1)

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
A=[0]*N
B=[0]*N
a=0
b=N-1
for i in range(K):
  j=K-1-i
  while S[a]=='x':
    a+=1
  while S[b]=='x':
    b-=1
  A[i]=a
  a+=1+C
  B[j]=b
  b-=1+C
for i in range(K):
  if A[i]==B[i]:
    print(A[i]+1)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left, bisect_right

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

    L = [0] * (N + 2)
    R = [0] * (N + 2)
    # 1-indexedで管理した
    # 貪欲に端から配置した場合に達成可能な
    # 累積配置数

    need = [0] * N

    i = 0
    while i < N:
        if s[i] == 'o':
            L[i + 1] = 1
            need[i] += 1
            i += C + 1
        else:
            i += 1

    i = N - 1
    while i >= 0:
        if s[i] == 'o':
            R[i + 1] = 1
            need[i] += 1
            i -= C + 1
        else:
            i -= 1

    for i in range(N):
        L[i + 1] += L[i]
        R[i + 1] += R[i]

    ans = []
    for i in range(N):
        if need[i] == 2:
            li = bisect_left(L, L[i])  # 1-indexed
            if R[i + 1] == R[i + 2]:
                ri = bisect_right(R, R[i + 2]) + 1
            else:
                ri = i + 2  # 1-indexed
            d = (ri - li + 1 <= C)
            except_i = L[i] + (R[N] - R[i + 1]) - d
            if except_i < K:
                ans.append(i + 1)

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


if __name__ == '__main__':
    main()

# 前後両端について
# それぞれから貪欲に配置した累積配置数を準備
# 必ず働く日は
# 前から貪欲に配置したケースと
# 後ろから貪欲に配置したケースの重なりに含まれる必要があり、
# そのような重なり(need==2)について
# その日に働かないとした場合の前後の累積配置数の和がK未満なら働く必要がある

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)
        if len(L) == K:
            break
        i += C+1
    else:
        i += 1
i = N-1
while i >= 0:
    if S[i] == "o":
        R.append(i)
        if len(R) == K:
            break
        i -= C+1
    else:
        i -= 1
R.reverse()
for i in range(K):
    if L[i] == R[i]:
        print(L[i]+1)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, k, c = nm()
a = ns()

ans = []
al = []
count = 0
dey = 1
for i in a:
    if i is "o" and count <= 0:
        al.append(dey)
        count = c + 1
    dey += 1
    count -= 1
ar = []
count = 0
dey = n
for i in reversed(a):
    if i is "o" and count <= 0:
        ar.append(dey)
        count = c + 1
    dey -= 1
    count -= 1


al = al[:k]
ar = ar[:k]
for i in al:
    j = ar.pop(-1)
    if i == j:
        ans.append(i)
for i in ans:
    print(i)

Submission status: Accepted

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

#前から貪欲に
x = 0
L = [-1] * K
p = 0
while (x < N) and (p != K):
  if S[x] == "o":
    L[p] = x
    p += 1
    x += C + 1
  else:
    x += 1

#後ろから貪欲に    
y = N - 1
R = [-1] * K
q = 0
while (y > -1) and(q != K):
  if S[y] == "o":
    R[q] = y
    q += 1
    y -= C + 1
  else:
    y -= 1
    
#print(L, R)

#LとRの被っている数に1足したものを出力
for i in range(K):
  if L[i] == R[K - i - 1]:
    print(L[i] + 1)

Submission status: Accepted

Solution code:
def greedy_sche(read_dir=1):
    res = []
    i = 1 if read_dir == 1 else n 
    cnt = 1
    while cnt <= k:
        if s[i - 1]:
            res.append(i)
            cnt += 1
            i += read_dir * (c + 1)
        else:
            i += read_dir
    return res


n, k, c = map(int, input().split())
s = [c == 'o' for c in input()]
[print(f) for f, b in zip(greedy_sche(1), greedy_sche(-1)[::-1]) if f == b]

Submission status: Accepted

Solution code:
def greedy_sche(read_dir=1):
    res = []
    i = 1 if read_dir == 1 else n 
    cnt = 1
    while cnt <= k:
        if s[i - 1]:
            res.append(i)
            cnt += 1
            i += read_dir * (c + 1)
        else:
            i += read_dir
    return res


n, k, c = map(int, input().split())
s = [c == 'o' for c in input()]

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

Submission status: Accepted

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

L = {}
R = {}

# forward
i = 0
fk = 0
while i < n and fk < k:
  if s[i] == 'x':
    i += 1
  else:
    L[fk+1] = i
    i += (c + 1)
    fk += 1
    

# backward
n -= 1
while 0 <= n and 0 < k:
  if s[n] == 'x':
    n -= 1
  else:
    R[k] = n
    n -= (c + 1)
    k -= 1


keys = set(L.keys()) | set(R.keys())
for k in sorted(keys):
  if k in R and k in L:
    if R[k] == L[k]:
      print(R[k]+1)

Submission status: Accepted

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

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

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

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1

Submission status: Accepted

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

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

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

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1

Submission status: Accepted

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

L = []
R = []

i = -1
j = n  

for ki in range(k):
  while i < n:
    i += 1
    if s[i] == 'o':           
      L += [i]
      i += c
      break

for ki in range(k):      
  while 0 <= j:
    j -= 1
    if s[j] == 'o':          
      R += [j]
      j -= c
      break
      
for i in range(k):
  if L[i] == R[-i-1] :
    print(L[i]+1)

Submission status: Accepted

Solution code:

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

left = [ -1 for i in range(k)]
right = [ -1 for i in range(k)]

pointer = 0
for l in range(k):

  for s in range(pointer,n):
    if S[s] == 'o':
      left[l] = s
      pointer = s+c+1
      break

pointer = n-1
for r in range(k):

  for s in range(pointer,-1,-1):
    if S[s] == 'o':
      right[r] = s
      pointer = s-c-1
      break

for l,r in zip(left, right[::-1]):
  if l==r:
    print(l+1)

Submission status: Accepted

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)]
n=0
rc=0
lc=0
while True:
  if lc==K:
    break
  if S[n]=="o":
    L[lc]=n+1
    n+=C+1
    lc+=1
  else:
    n+=1
n=N-1
while True:
  if rc==K:
    break
  if S[n]=="o":
    R[K-1-rc]=n+1
    n-=C+1
    rc+=1
  else:
    n-=1
for i in range(K):
  if R[i]==L[i]:
    print(R[i])

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
#働く日のうちi日目についてそれ以後でないと働けない日をL[i]とする配列を考える
#働く日のうちi日目についてそれ以前でないと働けない日をR[i]とする配列も考える
#その二つが同じとき、必ず働かなければいけない日になる
#L[i]があった時、L[i]+c+1以降からしか働けないことに注意(vice versa)

#バグ？なんで？
l=[-1]*k
r=[-1]*k
nowl=0
indl=0
while nowl<n and indl<k:
    for i in range(nowl,n):
        if s[i]=="o":
            l[indl]=i
            nowl=i+c+1
            indl+=1
            break
nowr=n-1
indr=k-1
while nowr>=0 and indr>=0:
    for i in range(nowr,-1,-1):
        if s[i]=="o":
            r[indr]=i
            nowr=i-c-1
            indr-=1
            break
for i in range(k):
    if l[i]==r[i]:
        print(l[i]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MI=lambda:map(int,input().split())
n,k,c=MI()
s=input()

left=[];right=[]
i=0
while 0<=i<=n-1:
    if s[i]=="o":
        left+=(i),
        i+=c+1
    else:
        i+=1
j=n-1
while 0<=j<=n-1:
    if s[j]=="o":
        right+=j,
        j-=(c+1)
    else:
        j-=1

ans=list(set(left)&set(right))

if len(ans)>k:
    print()
else:
    for q in sorted(ans):
        print(q+1)

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
S_reverse = S[::-1]

left_justified = [-1 for _ in range(N)]
right_justified = [-2 for _ in range(N)]

for i_justified in (left_justified, right_justified):
    if i_justified == left_justified:
        i_S = S
        nearest_position = 1
        positioning = 1
    else:
        i_S = S_reverse
        nearest_position = K
        positioning = -1
    
    i_K = 0
    
    while i_K <= N-1:
        if i_S[i_K] == 'o':
            i_justified[i_K] = nearest_position
            i_K += C
            nearest_position += positioning
        i_K += 1

for i_N in range(N):
    if left_justified[i_N] == right_justified[N - i_N - 1]:
        print(i_N + 1)

Submission status: Accepted

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

F_list = []
B_list = []

f_count = 0
b_count = 0
f_rest = 0
b_rest = 0
S_len = len(S)
# o
for i in range(S_len):
    if f_count == K and b_count == K:
        break

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

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

Submission status: Accepted

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

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

wd = []
wdl = []

pw = 0
pwl = 0

for d in range(K):

    # 先詰めを探す
    while True:
        if S[pw] == ('o'):
            wd.append(pw)
            break
        pw += 1
    pw += C + 1
    
    # 後詰めを探す
    while True:
        if Sr[pwl] == ('o'):
            wdl.append((N-1) - pwl)
            break
        pwl += 1
    pwl += C + 1

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

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = list(input())
# cnt = s.count('o')
os = [i for i,x in enumerate(s) if x=='o']

from collections import deque

q = deque(os.copy())
_q1 = q.popleft()
m = k-1
l = [_q1]
if m > 0:
    while q:
        _q2 = q.popleft()
        if _q2 - _q1 > c:
            l.append(_q2)
            _q1 = _q2
            m -= 1
            if m == 0:
                q = deque([])
        else:
            pass

q = deque(os.copy())
_q2 = q.pop()
m = k-1
r = [_q2]
if m > 0:
    while q:
        _q1 = q.pop()
        if _q2 - _q1 > c:
            r.append(_q1)
            _q2 = _q1
            m -= 1
            if m == 0:
                q = deque([])
        else:
            pass

r = list(reversed(r))

ans = 0
for _l, _r in zip(l, r):
    if _l == _r:
        print(str(_l+1))
        ans = 1

if ans == 0:
    print()

Submission status: Accepted

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

def solve_dp(s):
  dp = [0]*(n+2)
  for i in range(n):
    if i <= c and s[i] == 'o':
      dp[i+1] = 1
    else:
      if s[i] == 'o':
        dp[i+1] = max(dp[i], dp[i-c]+1)
      else:
        dp[i+1] = dp[i]
  return dp

mae = solve_dp(s)
ushiro = solve_dp(s[::-1])[::-1]

for i in range(1,n+1):
  if mae[i-1] + ushiro[i+1] < k:
    print(i)

Submission status: Accepted

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

l, r = [], []
cur = 0
count = 0

while cur <= n:
    if s[cur] == "o":
        count += 1
        l.append((count, cur+1))
        cur += c

    cur += 1

cur = n
count = k

while cur >= 0:
    if s[cur] == "o":
        r.append((count, cur+1))
        count -= 1
        cur -= c

    cur -= 1

ans = (i[1] for i in set(l) & set(r))
for i in sorted(ans):
    print(i)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    input = stdin.readline
    n, k, c = map(int, input().split())
    s = input()

    l, r = [], []
    cur = 0
    count = 0

    while cur <= n:
        if s[cur] == "o":
            count += 1
            l.append((count, cur+1))
            cur += c

        cur += 1

    cur = n
    count = k

    while cur >= 0:
        if s[cur] == "o":
            r.append((count, cur+1))
            count -= 1
            cur -= c

        cur -= 1

    ans = (i[1] for i in set(l) & set(r))
    for i in sorted(ans):
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

right, left = [0 for _ in range(N)], [0 for _ in range(N)]

cnt = 0
work = 0
while True:
    if work == K:
        break
    if S[cnt] != "x":
        right[cnt] += 1
        work += 1
        cnt += C+1
    else:
        cnt += 1

S = list(reversed(S))

cnt = 0
work = 0
while True:
    if work == K:
        break
    if S[cnt] != "x":
        left[cnt] += 1
        work += 1
        cnt += C+1
    else:
        cnt += 1

left.reverse()
# print(right)
# print(left)

cnt1 = 0
cnt2 = 0
for i in range(N):
    if right[i] == 1:
        cnt1 += 1
    if left[i] == 1:
        cnt2 += 1
    if right[i] == left[i] == 1 and cnt1 == cnt2:
        print(i+1)

Submission status: Accepted

Solution code:
# import time

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

F = []
L = []

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

# print(t2 - t1, t3 - t2)

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

if len(F) == K and len(L) == K:
    ans = [i + 1 for i in set(F) & set(L)]
    if len(ans) != 0:
        ans.sort()
        [print(i) for i in ans]

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
N,K,C=map(int,input().split())
S=input()
S_R=S[::-1]
L=[]
R=[]
loop=0
cnt=0
while (loop<N):
	if S[loop]=="o":
		L.append(loop+1)
		cnt+=1
		loop+=C+1
	else:
		loop+=1
	if cnt>K:
		break
if cnt<K:
	exit()
loop=0
cnt=0

while (loop<N):
	if S_R[loop]=="o":
		R.append(N-loop)
		cnt+=1
		loop+=C+1
	else:
		loop+=1
	if cnt>K:
		break
if cnt<K:
	exit()

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

Submission status: Accepted

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

left, right = [], []
d = 0
while d < N and len(left) < K:
    if S[d] == 'o':
        left.append(d)
        d += C + 1
    else:
        d += 1
d = N - 1
while d >= 0 and len(right) < K:
    if S[d] == 'o':
        right.append(d)
        d -= C + 1
    else:
        d -= 1
right.sort()

ans = []
for i in range(K):
    if left[i] == right[i]:
        ans.append(left[i])

for c in ans:
    print(c+1)

Submission status: Accepted

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

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

for i in range(k):
    if left_dp[i] == right_dp[k-i-1]:
        print(left_dp[i])