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 copy
 
n,k,c = map(int,input().split())
s = list(input())
 
front = []
back = []
 
# 前から貪欲
j = copy.copy(k)
i = 0
while j > 0:
  if s[i] == "o":
    front.append(i)
    i += c+1
    j -= 1
  else:
    i += 1
 
# 後ろから貪欲
 
j = copy.copy(k)
i = n-1
while j > 0:
  if s[i] == "o":
    back.append(i)
    i -= c+1
    j -= 1
  else:
    i -= 1

back.sort()
for i in range(k):
  if front[i] == back[i]:
    print(front[i]+1)

Submission status: Accepted

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

l=[-99999999]
for i in range(n):
  if s[i]=='o':
    if l[-1]+c<i:
      l.append(i)
l=l[1:k+1]

l2=[99999999]
for i in range(n-1,-1,-1):
  if s[i]=='o':
    if l2[-1]-c>i:
      l2.append(i)
l2.reverse()
l2=l2[len(l2)-1-k:len(l2)-1]

for i in range(k):
  if l[i]==l2[i]:
    print(l[i]+1)

Submission status: Accepted

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

L = [0] * K
k = 0
i = 0
rest = C
while k < K:
    if rest >= C and S[i] == 'o':
        L[k] = i
        k += 1
        rest = 0
    else:
        rest += 1
    i += 1

R = [0] * K
k = K
i = N - 1
rest = C
while k > 0:
    if rest >= C and S[i] == 'o':
        R[k - 1] = i
        k -= 1
        rest = 0
    else:
        rest += 1
    i -= 1

ans = []
for k in range(K):
    if L[k] == R[k]:
        ans.append(L[k] + 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
SL=input()
SR=SL[::-1]
Left=[]
Right=[]
Last=-N-1
Rast=-N-1
cL=cR=0
for i in range(N):
    if SL[i]=="o" and i-Last>C and cL<=K:
        Left.append(i)
        Last=i
        cL+=1
    if SR[i]=="o" and i-Rast>C and cR<=K:
        Right.append(N-i-1)
        Rast=i
        cR+=1
Right=Right[::-1]

ans=[]
for k in range(K):
    if Left[k]==Right[k]:
        ans.append(Left[k]+1)

if len(ans)==0:
    print()
else:
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
import sys

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

# 前からと後ろからでgreedyにcandに入れて両方の一致したところ
N, K, C = lr()
S = sr()

def choose(S):
    cand = []
    count = 0
    cur = 0
    while cur < len(S):
        if S[cur] == 'o':
            count += 1
            cand.append(cur)
            cur += C+1            
        else:
            cur += 1
        if count >= K:
            break
    return cand

cand1 = choose(S)
cand2 = choose(S[::-1])[::-1]
cand2 = [N-1-x for x in cand2]

for x, y in zip(cand1, cand2):
    if x == y:
        print(x+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, K, C = map(int, input().split())
s = list(input())
llst = []
rlst = []

index = 0
lcnt = 0
while index < N:
    if s[index] == 'o':
        llst.append(index)
        index += C + 1
        lcnt += 1
        if lcnt == K:
            break
    else:
        index += 1
index = N - 1
rcnt = 0
while index >= 0:
    if s[index] == 'o':
        rlst.append(index)
        index -= (C + 1)
        rcnt += 1
        if rcnt == K:
            break
    else:
        index -= 1

ans = []
for i in range(len(llst)):
    if i <= len(rlst):
        if llst[i] == rlst[-i - 1]:
            ans.append(llst[i] + 1)
    else:
        break

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
ne=10**6*(-1)
fow=[]
bac=[]
for i in range(n):
    if i>ne and s[i]!="x":
        ne=i+c
        fow.append(i)
    if len(fow)==k:
        break
ne=10**6
for i in range(n-1,-1,-1):
    if i<ne and s[i]!="x":
        ne=i-c
        bac.append(i)
    if len(bac)==k:
        break
bac.sort()
for i,j in zip(fow,bac):
    if i==j:
        print(i+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    maxR[n] = rst
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    maxL[n] = rst
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if maxR[i] == -1:
        maxR[i] = dfs(i, C)

# if maxR[-1] == -1:
#     maxR[-1] = 0
# for i in range(N - 2, -1, -1):
#     if maxR[i] == -1:
#         maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if maxL[i] == -1:
        maxL[i] = dfs2(i, C)

# if maxL[0] == -1:
#     maxL[0] = 0
# for i in range(1, N):
#     if maxL[i] == -1:
#         maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    maxR[n] = rst
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    maxL[n] = rst
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if S[i] == 'o' and maxR[i] == -1:
        maxR[i] = dfs(i, C)

if maxR[-1] == -1:
    maxR[-1] = 0
for i in range(N - 2, -1, -1):
    if maxR[i] == -1:
        maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if S[i] == 'o' and maxL[i] == -1:
        maxL[i] = dfs2(i, C)

if maxL[0] == -1:
    maxL[0] = 0
for i in range(1, N):
    if maxL[i] == -1:
        maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

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

Submission status: Accepted

Solution code:
#働く日は左から順に貪欲にとると、前に詰める感じで最も効率が良い
#ベストな時、何日目に何回の勤労が始まったかを取れるため、i回目の勤労はL[i]日目以降になりうる、という配列Lをとれる
#一方右から貪欲にとると、何が起きるか
#一番右のoは最終日に働き、間隔を開け次のoを次の日に…というようにすると、
#これは後ろから詰める感じで効率が良いことがわかる
#よってi回目の労働はR[i]日目以前になりうる、という配列Rを取れる
#ここで、L,Rの構成可能性は約束されているので(やさしい)
#x回目の労働がL[i]日目以降R[i]日目以前という意味より、L[x]=R[x]の時はx回目の勤労はL[x]=R[x]日目にやらないといけないことを意味する
#(逆説的にL[x]!=R[x]ならばi回目は必ず違う勤労日を構成できることを意味する)
from collections import deque
N,K,C=map(int,input().split())
S=list(input())
L=deque()
l=[]
R=deque()
r=[]
i=0
while len(L)<K:
    if S[i]=="o":
        L.append(i)
        i=i+(C+1)
    else:
        i=i+1
i=N-1
while len(R)<K:
    if S[i]=="o":
        R.appendleft(i)
        i=i-(C+1)
    else:
        i=i-1
l=list(L)
r=list(R)
#print(l,r)
for i in range(K):
    if l[i]==r[i]:
        print(l[i]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k, c = map(int,input().split())
    S = input()
    dp = [0] * n
    for i in range(n-1, -1, -1):
        if S[i] == 'o':
            dp[i] = 1
            if i + c + 1 < n:
                dp[i] += dp[i + c + 1]
        else:
            dp[i] = dp[i + 1] if i + 1 < n else 0

    if max(dp) > k:
        return

    res = []
    now = 0
    while now < n:
        prev = now
        day = dp[now]
        cnt = 0
        fix = INF
        while now < n and dp[now] == day:
            if S[now] == 'o':
                fix = min(fix, now)
                cnt += 1
            now += 1
        if cnt == 1:
            now = fix + c + 1
            res.append(fix + 1)
        else:
            now = max(now, fix + c + 1)

    print(*res)
resolve()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
S = list(input())
rS = S[::-1]
lcnt = 0
left = [0] * n
rcnt = 0
right = [0] * n
llimit = -1
rlimit = -1
for i in range(n):
    if S[i] == "o" and llimit < i:
        lcnt += 1
        left[i] = lcnt
        llimit = i + c
    if rS[i] == "o" and rlimit < i:
        rcnt += 1
        right[-(i + 1)] = k + 1 - rcnt
        rlimit = i + c
for i in range(n):
    if left[i] == right[i] and left[i] > 0:
        print(i + 1)

Submission status: Accepted

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

asc = []
des = []

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

count = n-1
while count>=0:
    if s[count]=="o":
        des.append(count)
        count -= c+1
    else:
        count -= 1
des = des[0:k]
des.reverse()

# print(asc)
# print(des)

for i in range(len(asc)):
    if asc[i]==des[i]:
        print(asc[i]+1)

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

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
i=0
data1=[0 for i in range(0,N)]
if S[0]=='o':
    for j in range(0,C+1):
        if N>j:
            data1[j]=(1,min(N,C+1))
    i=C+1
else:
    data1[0]=(0,1)
    i=1
while N-1>=i:
    if S[i]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data1[i+j]=(data1[i-1][0]+1,min(i+C+1,N))
        i+=C+1
    else:
        data1[i]=(data1[i-1][0],i+1)
        i+=1

data2=[0 for i in range(0,N)]
if S[-1]=='o':
    for j in range(0,C+1):
        if N>j:
            data2[j]=1
    i=C+1
else:
    data2[0]=0
    i=1
while N-1>=i:
    if S[-i-1]=='o':
        for j in range(0,C+1):
            if N>i+j:
                data2[i+j]=data2[i-1]+1
        i+=C+1
    else:
        data2[i]=data2[i-1]
        i+=1

if N==1:
    print(1)
else:
    for i in range(0,N):
        if S[i]=='o':
            if i==0:
                if K>data2[N-2]:
                    print(i+1)
            elif N-1>i:
                work,nextday=data1[i-1]
                if nextday!=N:
                    nextday=max(nextday,i+1)
                    if K>work+data2[N-1-nextday]:
                        print(i+1)
                else:
                    if K>work:
                        print(i+1)
            elif i==N-1:
                if K>data1[N-2][0]:
                    print(i+1)

Submission status: Accepted

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

left = [0 for i in range(n + 1)]
right = [0 for i in range(n + 1)]

left[0] = 0
i = 1
cnt = 0
while i <= n:
    if s[i - 1] == 'o':
        cnt += 1
        for j in range(c + 1):
            left[i] = cnt
            i += 1
            if i == (n + 1):
                break
    else:
        left[i] = cnt
        i += 1

right[n] = 0
i = n - 1
cnt = 0
while i >= 0:
    if s[i] == 'o':
        cnt += 1
        right[i] = cnt
        for j in range(c + 1):
            right[i] = cnt
            i -= 1
            if i == -1:
                break
    else:
        right[i] = cnt
        i -= 1

# print(left)
# print(right)
for i in range(n):
    # skip i th element
    if left[i] + right[i + 1] >= k:
        continue
    print(i + 1)

Submission status: Accepted

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

ls = []
nex = -1
for i in range(N):
    if S[i] == "o" and i > nex:
        ls.append(i + 1)
        nex = i + C
        
    if len(ls) == K:
        break

rs = []
nex = N
for i in reversed(range(N)):
    if S[i] == "o" and i < nex:
        rs.append(i + 1)
        nex = i - C
        
    if len(rs) == K:
        break
        
for l, r in zip(ls, rs[::-1]):
    if l == r:
        print(l)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, k, c = map(int, args[0].split())
    S = args[1]

    work = [s == 'o' for s in S]
    L = []
    R = []

    i = 0
    while i < n and len(L) < k:
        if work[i]:
            L.append(i+1)
            i += c+1
        else:
            i += 1

    i = n-1
    while 0 <= i and len(R) < k:
        if work[i]:
            R.append(i+1)
            i -= c+1
        else:
            i -= 1

    return '\n'.join(str(l) for l, r in zip(L, R[::-1]) if l == r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

L = [-1] * K
interval = 0
cum = 0
for i in range(N):
    if S[i] == "o" and interval == 0:
        L[cum] = i
        interval = C
        cum += 1
        if cum >= K:
            break
    else:
        interval = max(0, interval - 1)

R = [-1] * K
interval = 0
cum = 0
for i in reversed(range(N)):
    if S[i] == "o" and interval == 0:
        R[-1 - cum] = i
        interval = C
        cum += 1
        if cum >= K:
            break
    else:
        interval = max(0, interval - 1)

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

Submission status: Accepted

Solution code:
def main():
    from itertools import groupby
    n, k, c = map(int, input().split())
    s = list(input())

    if c == 0:
        a = [i + 1 for i, c in enumerate(s) if c == 'o']
        if len(a) == k:
            print(*a, sep='\n')
        else:
            print()
        exit()

    check_f = []
    x = 0
    for i, j in enumerate(s, 1):
        if x:
            x -= 1
            continue
        if j == 'o':
            x = c
            check_f.append(i)
        if len(check_f) == k:
            break

    check_b = []
    x = 0
    for i, j in enumerate(s[::-1]):
        if x:
            x -= 1
            continue
        if j == 'o':
            x = c
            check_b.append(n - i)
        if len(check_b) == k:
            break

    ans = list(set(check_f) & set(check_b))
    ans.sort()
    ans = '\n'.join(map(str, ans))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Left=[0]*k
Leftcnt=0
Right=[0]*k
Rightcnt=0

Rest=['x']*c

#前から
L=copy.deepcopy(s)
for i in range(n):
    if Leftcnt==k:
        break
    if L[i]=='o':
        Left[Leftcnt]=i+1
        Leftcnt+=1
        if i+c<=n:
            L[i+1:i+c+1]=Rest

#後ろから
R=copy.deepcopy(s)
for j in range(n):
    if Rightcnt==k:
        break
    if R[-j-1]=='o':
        Right[Rightcnt]=-j+n
        Rightcnt+=1
        if j+c<=n:
            R[-j-c-1:-j-1]=Rest
Right=sorted(Right)
for i in range(k):
    if Left[i]==Right[i]:
        print(Left[i])

Submission status: Accepted

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

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

i = len(s) - 1
while True:
    if s[i] == 'o':
        l_list.append(i)
        if len(l_list) == k:
            break
        i -= c + 1
    else:
        i -= 1

l_list.sort()

for i in range(len(f_list)):
    if f_list[i] == l_list[i]:
        print(f_list[i]+1)

Submission status: Accepted

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

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

right = []
cnt = 0
now = len(s)-1
while(cnt < k):
    if(s[now]=='o'):
        right.append(now)
        cnt += 1
        now -= c
    now -= 1

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

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()

cnt = 0
i = n-1
d = defaultdict(int)
tmp = k
while i >= 0:
    if s[i] == 'o':
        cnt += 1
        d[tmp] = i
        tmp -= 1
        i -= c
    i -= 1
i = 0
f = defaultdict(int)
tmp = 1
while i < n:
    if s[i] == 'o':
        f[tmp] = i
        tmp += 1
        i += c
    i += 1
for i,j in f.items():
    if d[i] == j:
        print(j+1)

Submission status: Accepted

Solution code:
#!python3

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


def main():
    L = [None] * K
    for i in range(N):
        if S[i] == "o":
            L[0] = i
            break            
    for i in range(1, K):
        j = L[i-1] + C + 1
        while S[j] == "x":
            j += 1
        L[i] = j
    
    R = [None] * K
    for i in range(N - 1, -1, -1):
        if S[i] == "o":
            R[-1] = i
            break
    for i in range(K - 2, -1, -1):
        j = R[i+1] - C - 1
        while S[j] == "x":
            j -= 1
        R[i] = j
    
    for i in range(K):
        if L[i] == R[i]:
            print(L[i] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count = set()

for num, i in enumerate(tmp):
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        count.add(num)
        wait = c
        last_day -= 1
        if last_day == 0:
            break

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count2 = set()
for num, i in enumerate(reversed(tmp)):
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        count2.add(n - num - 1)
        wait = c
        last_day -= 1
        if last_day == 0:
            break

count = list(count)
count2 = list(count2)
count.sort()
count2.sort()
ans = []
for i in range(len(count)):
    if count[i]==count2[i]:
        ans.append(count[i]+1)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()


## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def Primes(x):
    div=[1]
    for j,c in primeFactor(x).items():
        tmp=[]
        for x in div:
            for k in range(1,c+1):
                tmp+=[x*j**k]
        div+=tmp
    return div



show_flg=False
show_flg=True

ans=0

n,k,c=LI()
s=input()

def lbd(s,n,k,c):
    dp=[[0] for i in range(n+1)]
    dp=[0]*n
    mdp=[0]*n
    for i in range(n):
        if s[i]=='o':
            dp[i]=1
            if i-c-1>=0:
                dp[i]=mdp[i-c-1]+1
            mdp[i]=max(mdp[i-1],dp[i])
        else:
            dp[i]=dp[i-1]
            mdp[i]=max(mdp[i-1],dp[i])
    return dp        

dp1=lbd(s,n,k,c)
dp2=lbd(s[::-1],n,k,c)[::-1]

if n==1:
    if k==1 and s=='o':
        print(1)
    exit()

for i in range(n):
    if s[i]=='x':
        continue
    if i==0:
        D=dp2[i+1]
    elif i==n-1:
        D=dp1[i-1]
    else:
        D=dp1[i-1]+dp2[i+1]
    
    if D<k:
        print(i+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, K, C = [int(i) for i in input().split()]
S = input()
ok_days = []
fdp = []
bdp = []

for ind, s in enumerate(S):
    if(s=='o'):
        ok_days.append(ind+1)

last = 0
fseen = set()
for i in ok_days:
    if(i>last):
        fseen.add(i)
        last = i+C

last = ok_days[-1]+1
bseen = set()
for i in ok_days[::-1]:
    if(i<last):
        bseen.add(i)
        last = i-C

ans = fseen&bseen
if(len(fseen)<=K and len(bseen)<=K):
    for i in sorted(list(ans)):
        print(i)

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = input()
S_l = len(S)
from collections import deque
L = [0]*K
R = [0]*K

period = C
j = 0
for i in range(S_l):
  if j==K:
    break
  if S[i]=='x':
    period+=1
    continue
  else:
    if period<C:
      period+=1
      continue
    else:
      period=0
      L[j]=i
      j+=1
      
S = S[::-1]
period = C
j = 0
for i in range(S_l):
  if j==K:
    break
  if S[i]=='x':
    period+=1
    continue
  else:
    if period<C:
      period+=1
      continue
    else:
      period=0
      R[K-1-j] = S_l - 1 - i
      j+=1
      

for i,j in zip(L,R):
  if i==j:
    print(i+1)

Submission status: Accepted

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

l = []
r = []

cnt = 0
for i in range(n):
    if cnt == 0 and s[i] == 'o':
        cnt = c
        l.append(i)
    else:
        cnt = max(0,cnt-1)
    if len(l) == k:
        break
cnt = 0
for i in range(n-1,-1,-1):
    if cnt == 0 and s[i] == 'o':
        cnt = c
        r.append(i)
    else:
        cnt = max(0,cnt-1)
    if len(r) == k:
        break
r.reverse()

#print(l,r)

for i in range(k):
    if l[i] == r[i]:
        print(l[i]+1)

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

import numpy as np
N, K, C=map(int, input().split())
s=list(input())

forward=np.zeros(K)
back=np.zeros(K)

day=0
count=0
while day <N and count<K:
    if s[day]=='o':
        forward[count]=day
        count+=1
        day+=C+1
    else:
        day+=1

day=N-1
count=0
while day<N and count<K:
    if s[day]=='o':
        back[count]=day
        count+=1
        day-=C+1
    else:
        day-=1

#print(forward)
#print(back[::-1])

for i in range(K):
    if forward[i]==back[K-1-i]:
        print(int(forward[i])+1)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
l=[0]*k
r=[0]*k
rest=0
work=0
for i in range(n):
  rest = max(rest-1,0)
  if s[i]=='o' and rest==0 and work < k:
    l[work]=i+1
    work+=1
    rest+=c+1
rest=0
work=0
for i in range(n-1,-1,-1):
  rest = max(rest-1,0)
  if s[i]=='o' and rest==0 and work < k:
    r[k-work-1]=i+1
    work+=1
    rest+=c+1
for i in range(k):
  if l[i]==r[i]:
    print(l[i])

Submission status: Accepted

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

while True:
    if S[hi] == 'o':
        mae[youso] = hi+1
        youso += 1
        if youso == K:
            break
        hi += C
    hi += 1

hi = N-1
youso = 0

while True:
    if S[hi] == 'o':
        ushiro[youso] = hi+1
        youso += 1
        if youso == K:
            break
        hi -= C
    hi -= 1
ushiro.reverse()

for j in range(len(mae)):
    if mae[j] == ushiro[j]:
        print(mae[j])

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = [True if i == "o" else False for i in input()]
front = [0] * n
back = [0] * n
count = 0

day = 0
while day < n:
    if s[day]:
        front[day] = 1
        day += c+1
        count += 1
    else:
        day += 1

day = n-1
while day >= 0:
    if s[day]:
        back[day] = 1
        day -= c+1
    else:
        day -= 1
if count == k:
    for i in range(n):
        if front[i] == 1 and back[i] == 1:
            print(i+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)


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

    def forward(k):
        i = 0
        day = 0
        days = [-1] * k
        l = len(S)
        while day < k and i < l:
            while S[i] == 'x':
                i += 1
                if i >= l:
                    return None
            days[day] = i
            day += 1
            i += 1 + C
        if day < k:
            return None
        return days

    def backward(k):
        day = k
        days = [-1] * k
        l = len(S)
        i = l - 1
        while day > 0 and i >= 0:
            while S[i] == 'x':
                i -= 1
                if i < 0:
                    return None
            day -= 1
            days[day] = i
            i -= (1 + C)
        if day > 0:
            return None
        return days

    left = forward(K)
    if left is None:
        return

    right = backward(K)
    for i, j in zip(left, right):
        if i == j:
            print(i + 1)

main()

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)

if len(ansl) > k:
    print()
    exit()
# 後貪欲
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 a in sorted(list(set(ansl) & set(ansl2))):
    print(a+1)

Submission status: Accepted

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

a = set()
cnt = 0
for i,x in enumerate(s[::-1]):
    j = n - i
    if cnt > 0:
        cnt -= 1
    elif x == 'o':
        cnt += c
        a.add(j)

b = set()
cnt = 0
for i,x in enumerate(s):
    if cnt > 0:
        cnt -= 1
    elif x == 'o':
        cnt += c
        b.add(i+1)

if len(a)==k:
	print(*sorted(list(a&b)),sep="\n")
else:
	exit()