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()
fro = []
bac = []

for i in range(n):
    if s[i] == "o" and (len(fro) == 0 or fro[-1]+c < i):
        fro.append(i)
    if s[n-i-1] == "o" and (len(bac) == 0 or bac[-1]-c > n-i-1):
        bac.append(n-i-1)

for i in range(k):
    if fro[i] == bac[k-i-1]:
        print(fro[i]+1)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = input()
forth = set()
reverse = set()
cur = 0
tired = 0
for i in range(n):
    if s[i] == "o":
        if tired == 0:
            cur += 1
            tired = c
            forth.add(i+1)
        else:
            if tired > 0:
                tired -= 1
    else:
        if tired > 0:
            tired -= 1
if cur > k:
    exit()
s = s[::-1]
cur = 0
tired = 0
for i in range(n):
    if s[i] == "o":
        if tired == 0:
            cur += 1
            tired = c
            reverse.add(n-i)
        else:
            if tired > 0:
                tired -= 1
    else:
        if tired > 0:
            tired -= 1
ans = forth & reverse
ans = list(ans)
ans.sort()
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N,K,C = map(int, input().split())
S = input()
w = []
for i in range(len(S)):
   if S[i]=="o":
      w.append(i)
# print(w)
# early date
early = []
tmpwd = -1
for i in range(len(w)):
   if len(early) >= K:
      continue
   if tmpwd<0:
      tmpwd = w[i]
   elif w[i]>tmpwd+C:
      tmpwd = w[i]
   else:
      continue
   early.append(w[i])
# print(early)

# later date
late = []
tmpwd = -1
for i in reversed(range(len(w))):
   if len(late)>=K:
      continue      
   if tmpwd < 0:
      tmpwd = w[i]
   elif w[i] < tmpwd-C:
      tmpwd = w[i]
   else:
      continue
   late.append(w[i])

wd = set(early) & set(late)
early.sort()
late.sort()
# print(early,late)
for i in range(K):
   if early[i]==late[i]:
      print(early[i]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding: utf-8

# def debug(arg):
#     if __debug__:
#         pass
#     else:
#         import sys
#         print(arg, file=sys.stderr)
        
def main():
    N, K, C = map(int, input().split())
    S = dict(enumerate(str(input()), 1))

    sr = list(k for k, v in S.items() if v == 'o')
    sl = list(reversed(sr.copy()))

    l = [sl.pop()]
    r = [sr.pop()]
    
    for x in range(1, K):
        while True:
            ll = sl.pop()
            if ll > l[x - 1] + C:
                l.append(ll)
                break
        while True:
            rr = sr.pop()
            if rr < r[x - 1] - C:
                r.append(rr)
                break

    for ll, rr in zip(l, reversed(r)):
        if ll == rr:
            print(ll)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding: utf-8

def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)
        
def main():
    N, K, C = map(int, input().split())
    S = dict(enumerate(str(input()), 1))

    sr = list(k for k, v in S.items() if v == 'o')
    sl = list(reversed(sr.copy()))

    debug(sr)
    debug(sl)

    l = [sl.pop()]
    r = [sr.pop()]
    
    for x in range(1, K):
        while True:
            ll = sl.pop()
            if ll > l[x - 1] + C:
                l.append(ll)
                break
        while True:
            rr = sr.pop()
            if rr < r[x - 1] - C:
                r.append(rr)
                break

    debug(r)
    debug(l)

    # a = sorted(set(l) & set(r))

    # debug(a)
    # for aa in a:
    #     print(aa)
    
    for ll, rr in zip(l, sorted(r)):
        if ll == rr:
            print(ll)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
dpl = []
dpr = []
ans = []
count = 0
i = 0
while count < k:
    if s[i]=="o":
        dpl.append(i)
        count += 1
        i += c+1
    else: i += 1
count = 0
i = n-1
while count < k:
    if s[i]=="o":
        dpr.append(i)
        count += 1
        i += -c-1
    else: i -= 1
dpr.sort()
for i in range(len(dpl)):
    if dpl[i] == dpr[i]: ans.append(dpl[i]+1)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def resolve():
    N, K, C = lr()
    S = [i+1 for i, s in enumerate(sr()) if s == 'o']
    l = [S[0]]
    for i in S[1:]:
        if l[-1]+C >= i or len(l) > K:
            continue
        l.append(i)
    S = S[::-1]
    r = [S[0]]
    for i in S[1:]:
        if r[-1]-C <= i or len(r) > K:
            continue
        r.append(i)
    r = r[::-1]
    for i in range(K):
        if l[i] == r[i]:
            print(l[i])
resolve()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)


def input(): return sys.stdin.readline().rstrip()


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

L = [None] * K
R = [None] * K

i = 0
for j in range(N):
    if S[j] == 'o' and i < K and (i == 0 or j - L[i - 1] > C):
        L[i] = j
        i += 1

i = K - 1
for j in reversed(range(N)):
    if S[j] == 'o' and i >= 0 and (i == K - 1 or R[i + 1] - j > C):
        R[i] = j
        i -= 1

for l, r in zip(L, R):
    if l == r:
        print(l + 1)

Submission status: Accepted

Solution code:
def main():
    N, K, C = map(int, input().split())
    S = input()
    ansL = [0] * K
    pos = 0
    idx = 0
    while idx < K:
        if S[pos] == "o":
            ansL[idx] = pos
            idx += 1
            pos += C + 1
        else:
            pos += 1
    ansR = [0] * K
    pos = N-1
    idx = K-1
    while idx >= 0:
        if S[pos] == "o":
            ansR[idx] = pos
            idx -= 1
            pos -= C + 1
        else:
            pos -= 1
    for i in range(K):
        if ansL[i] == ansR[i]:
            print(ansL[i] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
x,y=[0]*n,[0]*n
work1,work2=[],[]
last=-10**9;cnt=0
for i in range(n):
    if s[i]=="o" and i-last>c:
        cnt+=1
        last=i
        work1.append(i)
    if cnt==k: break

nextw=10**9;cnt=0
for i in range(n-1,-1,-1):
    if s[i]=="o" and nextw-i>c:
        work2.append(i)
        cnt+=1
        nextw=i
    if cnt==k: break

work2.reverse()
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()

dp = [0]*(N+1)
dpr = [0]*(N+1)
for i in range(1,N+1):
    if S[i-1] == 'o':
        p = max(i-C-1,0)
        if dp[i-1] < dp[p] + 1:
            dp[i] = dp[p] + 1
            dpr[i] = i + C
            continue
    dp[i] = dp[i-1]
    dpr[i] = dpr[i-1]

rdp = [0]*(N+2)

for i in range(N,-1,-1):
    if S[i-1] == 'o':
        rdp[i] = max(rdp[i+1],rdp[min(N+1,i+C+1)]+1)
    else:
        rdp[i] = rdp[i+1]

ans = []
for i in range(1,N+1):
    if dp[i-1] + rdp[max(i+1,min(dpr[i-1]+1,N+1))] < K:
        ans.append(i)

for a in ans:
    print(a)

Submission status: Accepted

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

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

    right.reverse()


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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = list(input())
S_work = []
s = []
f = []
i = 0
while len(s) < K:
  if S[i] == "o":
    s.append(i)
    i += C + 1
  elif S[i] == "x":
    i += 1
  elif i == len(S):
    break
i = 1
while len(f) < K:
  if S[N - i] == "o":
    f.append(N - i)
    i += C + 1
  elif S[N - i] == "x":
    i += 1
  elif i == len(S):
    break
f.sort()
for i in range(K):
  if s[i] == f[i]:
    print(s[i] + 1)

Submission status: Accepted

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


def solve(N: int, K: int, C: int, S: str):
    l = [None] * N
    r = [None] * N

    pre = -float('inf')
    k = -1
    for cur in range(N):
        if cur - pre > C and S[cur] == 'o':
            k += 1
            pre = cur
            l[k] = cur

    pre = float('inf')
    k = K
    for cur in range(N-1, -1, -1):
        if pre - cur > C and S[cur] == 'o':
            k -= 1
            pre = cur
            r[k] = cur

    return [ll+1 for ll, rr in zip(l[:K], r[:K]) if ll == rr]
    


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    print(*solve(N, K, C, S), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

while len(r)<k and j<n:   
    if s[-j-1]=='o':
      r.append(n-j)
      j+=c+1
    else: j+=1
for n in range(k):
  if l[n]==r[-n-1]:
    print(l[n])

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
l=[0]*n
pre=n+c+1
cnt=k
for i in range(n-1,-1,-1):
    if s[i]=="o" and -(i)+pre>c and cnt>0:
        pre=i
        l[i]=cnt
        cnt-=1
pre=-c-5
cnt=0
for i in range(n):
    if s[i]=="o" and i-pre>c and cnt<k:
        pre=i;cnt+=1
        if l[i]==cnt:print(i+1)

Submission status: Accepted

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


cnt0 = [-10**10] * len(s)
cnt1 = [-10**10] * len(s)
rest0 = c
rest1 = c
ct0 = 1
ct1 = 1
for i in range(len(s)):
    a = s[i]
    b = s[len(s) - 1 - i]
    if (c <= rest0) & (a == 'o'):
        cnt0[i] = ct0
        ct0 += 1
        rest0 = 0
    else:
        rest0 += 1
    if (c <= rest1) & (b == 'o'):
        cnt1[len(s) - 1 - i] = ct1
        ct1 += 1
        rest1 = 0
    else:
        rest1 += 1
for i in range(len(s)):
    if (cnt0[i] + cnt1[i] == k+1):
        print(i+1)

Submission status: Accepted

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

F = {}
i = 0
c = 1
while i < N and c <= K:
    if S[i] == 'x':
        i += 1
        continue
    F[c] = i + 1
    i += C + 1
    c += 1

L = {}
i = N - 1
c = K
while i >= 0 and c >= 1:
    if S[i] == 'x':
        i -= 1
        continue
    L[c] = i + 1
    i -= C + 1
    c -= 1

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

Submission status: Accepted

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

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

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

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

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

#左側から〇を数える
left=[0]*n
rest=0
cnt=0

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

#右側から〇を数える
right=[0]*n
rest=n-1
cnt=0

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

#-1日目、n+1日目がエラーにならないように0を足す        
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()
L, R = [-1] * K, [-1] * K
k = 0; temp = -C
for i, s in enumerate(S, 1):
    if s == 'o' and i > temp + C: L[k] = i; k += 1; temp = i
    if k == K: break
k = K - 1; temp = N + C + 1
for i, s in reversed(list(enumerate(S, 1))):
    if s == 'o' and i < temp - C: R[k] = i; k -= 1; temp = i
    if k == -1: break
ans = []
for l, r in zip(L, R):
    if l == r: ans.append(l)
for a in ans: print(a)

Submission status: Accepted

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

A = [0]*N
B = [0]*N

i = 0
a = 1
while i < N:
    if S[i] == 'o':
        A[i] = a
        a += 1
        i += C+1
    else:
        i += 1
j = N-1
b = K
while j >= 0:
    if S[j] == 'o':
        B[j] = b
        b -= 1
        j -= C+1
    else:
        j -= 1

for i in range(N):
    if A[i] == B[i] and A[i] != 0:
        print(i+1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_e

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

left = []
i = 0
while K > len(left):
    while True:
        if S[i] == 'o':
            left.append(i)
            i += C + 1
            break
        i += 1

right = []
i = N - 1
while K > len(right):
    while True:
        if S[i] == 'o':
            right.append(i)
            i -= (C + 1)
            break
        i -= 1

right.reverse()

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

Submission status: Accepted

Solution code:
n, k, c = [int(i) for i in input().split()]
s = input()

work1 = [0] * k
work2 = [0] * k
cnt = 0
day = 0

while cnt < k:
	if s[day] == 'o':
		work1[cnt] = day
		cnt	+= 1
		day += (c+1)
	else:
		day += 1


cnt = k-1
day = n-1

while cnt >= 0:
	if s[day] == 'o':
		work2[cnt] = day
		cnt	-= 1 
		day -= (c + 1)
	else:
		day -= 1


for i in range(k):
	if work1[i] == work2[i]:
		print(work1[i]+1)

Submission status: Accepted

Solution code:
def main():
    n, k, c = map(int, input().split())
    s = input().rstrip()
    frnt = [None]*n
    back = [None]*n
    if s[0] == "o":
        frnt[0] = [1, 0]
    else:
        frnt[0] = [0, -1*n - 100]
    for i in range(1, n):
        if s[i] == "o" and i - frnt[i-1][1] - 1 >= c:
            frnt[i] = [frnt[i-1][0]+1, i]
        else:
            frnt[i] = [frnt[i-1][0], frnt[i-1][1]]
    if s[-1] == "o":
        back[-1] = [1, n-1]
    else:
        back[-1] = [0, 2*n + 100]
    for i in reversed(range(n-1)):
        if s[i] == "o" and back[i+1][1] - i - 1 >= c:
            back[i] = [back[i+1][0]+1, i]
        else:
            back[i] = [back[i+1][0], back[i+1][1]]
    for i in range(n):
        if s[i] == "x":
            continue
        a = frnt[i][0] + back[i][0]
        if i == frnt[i][1]:
            a -= 1
        if i == back[i][1]:
            a -= 1
        if i != frnt[i][1] and i != back[i][1]:
            if back[i][1] - frnt[i][1] - 1 < c:
                a -= 1
        if a == k-1:
            print(i+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lst = []
for i in range(n):
    if s[i]=='o':
        lst.append(i+1)

x,y = [],[]
for i in range(len(lst)):
    if i==0:
        x.append(lst[i])
    else:
        if lst[i]-x[-1]>c:
            x.append(lst[i])
    if len(x)==k:
        break

for i in range(len(lst))[::-1]:
    if i==len(lst)-1:
        y.append(lst[i])
    else:
        if y[-1]-lst[i]>c:
            y.append(lst[i])
    if len(y)==k:
        break

x.sort()
y.sort()

ans = []
for i in range(k):
    if x[i]==y[i]:
        ans.append(x[i])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N, K, C = [int(input_) for input_ in input().split(" ")]
    
tick_cross = input()
    
def find_earliest_work_days(K, C, tick_cross):
    """
    Find the list of the earliest day in all possible days for the n-th 
    work day.
    
    Parameters:
    K (int): The number of work days.
    C (int): Minimum interval between the previous work day and the 
             next work day.
    tick_cross (str): The character string of days he can go to work.
             
    Returns:
    List[int]: The list of the earliest day in all possible days for 
               the n-th work day.
    """
    
    N = len(tick_cross)
        
    day = 0
    earliest_work_days = []
    number_of_work_days = len(earliest_work_days)
    while (day < N) and (number_of_work_days < K):
        if tick_cross[day] == "o":
            earliest_work_days.append(day+1)
            number_of_work_days = len(earliest_work_days)
            day += C + 1
        else:
            day += 1
            
    return earliest_work_days
    
def find_latest_work_days(K, C, tick_cross): 
    """
    Find the list of the latest day in all possible days for the n-th 
    work day.
    
    Parameters
    K (int): The number of work days.
    C (int): Minimum interval between the previous work day and the 
             next work day.
    tick_cross (str): The character string of days he can go to work.
             
    Returns:
    List[int]: The list of the latest day in all possible days for 
               the n-th work day.
    """
    
    N = len(tick_cross)
        
    day = N - 1
    latest_work_days = []
    number_of_work_days = len(latest_work_days)
    while (day >= 0) and (number_of_work_days < K):
        if tick_cross[day] == "o":
            latest_work_days.append(day+1)
            number_of_work_days = len(latest_work_days)
            day -= (C + 1)
        else:
            day -= 1
            
    return sorted(latest_work_days)
                
earliest_work_days = find_earliest_work_days(K, C, tick_cross)
latest_work_days = find_latest_work_days(K, C, tick_cross)
for earliest, latest in zip(earliest_work_days, latest_work_days):
    if earliest == latest:
        print(earliest)

Submission status: Accepted

Solution code:
num=list(map(int, input().split()))
string=input()
countl=0
countr=num[1]
i=0
j=num[0]
L=[]
R=[]
#rR=[]
while countl!=num[1]:
  if string[i]=='o':
    L.append(i+1)
    countl=countl+1
    i=i+num[2]+1
  else:
    i=i+1
  if i>=num[0]:
    break
while countr!=0:
  if string[j-1]=='o':
    R.append(j)
    countr=countr-1
    j=j-num[2]-1
  else:
    j=j-1
  if j<0:
    break
#print(R)
R.reverse()
#print(L)
#print(rR)
for k in range(num[1]):
  if L[k]==R[k]:
    print(L[k])

Submission status: Accepted

Solution code:
data = input().split(" ")
N, K, C = int(data[0]), int(data[1]), int(data[2])
S = input()

point = 0
work_start = [0] * (K + 1)
for i in range(1, K + 1):
  point = S.find("o", point, N)
  work_start[i] = point + 1
  point += (C + 1)

point = N
work_end = [0] * (K + 1)
for i in range(K, 0, -1):
  point = S.rfind("o", 0, point)
  work_end[i] = point + 1
  point -= C

for i in range(1, K + 1):
  if work_start[i] == work_end[i]:
    print(work_start[i])

Submission status: Accepted

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

L = []
R = []

count_L = C
count_R = C

for i in range(N):
    if S[i] == "o" and count_L >= C:
        count_L = 0
        L.append(i)
    else:
        count_L += 1
        
    if S[N-i-1] == "o" and count_R >= C:
        count_R = 0
        R.append(N-i-1)
    else:
        count_R += 1
        
    if len(L) >= K and len(R) >= K:
        break
    
for l, r in zip(L, R[::-1]):
    if l == r:
        print(l+1)

Submission status: Accepted

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

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


date = 1

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

date = 1

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

for i in range(K):
    f = fastest.popleft()
    l = latest.pop()
    if f == l:
        print(f)

Submission status: Accepted

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

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


date = 1

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

date = 1

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

fastest = list(fastest)
latest = list(latest)

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

Submission status: Accepted

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

fastest = []
latest = []


date = 1

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

date = 1

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

Submission status: Accepted

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

l=[0]*n
r=[0]*n
i=0
j=n-1
cnt=0
while i<n:
    if s[i]=='x':
        i+=1
    if s[i]=='o':
        l[i]=1
        i+=c+1
        cnt+=1
#前から働いていって、必要以上の数働ける形の場合、必須となる日はありません。
if cnt>k:
    sys.exit()
    
while j>=0:
    if s[j]=='x':
        j-=1
    if s[j]=='o':
        r[j]=1
        j-=c+1
"""
ここまでで、lには「最速でその日に仕事ができる」
rには「遅くともその日までには仕事しないといけない」
というリストができます。

print(l)
print(r)
"""
for _ in range(len(l)):
    if l[_] and r[_]:
        print(_+1)

Submission status: Accepted

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

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

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

cnt1 = 0
i = 0
while cnt1 < k:
    if s[i] == "o":
        if l2[i] == cnt1 + 1:
            print(i+1)
        i += c + 1
        cnt1 += 1
    else:
        i += 1

Submission status: Accepted

Solution code:
# 解説AC
N,K,C = map(int, input().split())
S = [""] + list(input())

# cnt1[i]: [1,i]での最大労働可能日数
cnt1 = [0] * (N + 2)
cnt, can = 0, 0
for i in range(1, len(S)):
    if S[i] == "o" and i >= can:
        cnt += 1
        can = i + (C + 1)
    cnt1[i] = cnt

# cnt2[i]: [i,N]での最大労働可能日数
cnt2 = [0] * (N + 2)
cnt, can = 0, N
for i in range(len(S) - 1, 0, -1):
    if S[i] == "o" and i <= can:
        cnt += 1
        can = i - (C + 1)
    cnt2[i] = cnt

ans = []
for i, s in enumerate(S[1:], 1):
    if s == "x": continue
    # i日目に働かないと、条件を満たさない場合
    if cnt1[i - 1] + cnt2[i + 1] < K:
        ans.append(i)

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

Submission status: Accepted

Solution code:
n,nWorks,nSp = map(int,input().split())

s = input()

leftList = [0]*n
rightList = [0]*n

num = 0
count = 0

while num < n:
    if s[num] == "o":
        leftList[num] = 1
        count +=1
        num += 1 + nSp
    else:
        num +=1

if count > nWorks:
    exit()

num = n-1
count = 0
while num >= 0:
    if s[num] == "o":
        rightList[num] = 1
        count +=1
        num -= (1 + nSp)
    else:
        num -=1

for kk in range(n):
    if leftList[kk] and rightList[kk]:
        print(kk+1)

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = [1 if a == "o" else 0 for a in input()]

c = 0
X = [0] * N
Y = [0] * N

i = 0
while i < N:
    if S[i]:
        c += 1
        X[i] = 1
        i += C + 1
    else:
        i += 1

if c > K:
    exit()

i = N - 1
while i >= 0:
    if S[i]:
        Y[i] = 1
        i -= C + 1
    else:
        i -= 1

for i in range(N):
    if X[i] and Y[i]:
        print(i + 1)

Submission status: Accepted

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

mae, usiro = [-1] * n, [-1] * n

now, at = 1, 0
while at < n:
    if s[at] == 'x':
        at += 1
    else:
        mae[at] = now
        at += c + 1
        now += 1
        if now > k:
            break

now, at = k, n-1
while at >= 0:
    if s[at] == 'x':
        at -= 1
    else:
        usiro[at] = now
        at -= c + 1
        now -= 1
        if now <= 0:
            break

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

Submission status: Accepted

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

def solve(List):
    ans = []
    i = 0
    while i < N:
        if List[i] == 'o':
            ans.append(i+1)
            i += C
        i += 1
    return ans

n = solve(S)

if len(n) > K:
    pass
else:
    r = solve(S[::-1])
    r = list(map(lambda x: N+1-x, r[::-1]))
    ans = list(set(n) & set(r))
    ans.sort()
    for i in ans:
        print(i)

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
N, K, C = [int(s) for s in inputs]
input_line = input()
s = list(input_line)

L = []
i = 1
k = 0
while i<=N:
    if s[i-1]=='o':
        L.append(i)
        i += (C+1)
        k += 1
        if k==K:
            break
    else:
        i += 1

R = []
i = N
k = 0
while i>0:
    if s[i-1]=='o':
        R.append(i)
        i -= (C+1)
        k += 1
        if k==K:
            break
    else:
        i -= 1
R = R[::-1]

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

if C == 0 :
  if K == S.count('o') :
    for i, s in enumerate(S) :
      if s == 'o' :
        print(i + 1)

else :
  N += 2
  S = 'x' + S + 'x'

  dpL = [0] * N
  dpR = [0] * N
  for l in range(1, N) :
    r = N - 1 - l
    dpL[l] = max(dpL[l - 1], int(S[l] == 'o'))
    dpR[r] = max(dpR[r + 1], int(S[r] == 'o'))
    if l - C - 1 >= 0 and S[l] == 'o' :
      dpL[l] = max(dpL[l], dpL[l - C - 1] + 1)
    if r + C + 1 < N and S[r] == 'o' :
      dpR[r] = max(dpR[r], dpR[r + C + 1] + 1)

  h = []
  for r in range(C + 1) :
    heappush(h, (-dpR[r], r))

  for l in range(1, N) :
    r = l - 1 + C + 1
    if r < N :
      cost = dpL[l - 1] + dpR[r]
    else :
      cost = dpL[l - 1]
    heappush(h, (-cost, r))
    while h[0][1] <= l :
      heappop(h)
    
    if -h[0][0] < K and S[l] == 'o' :
      print(l)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
fo = []
ba = []
r = 0
for ind, cc in enumerate(s):
    ind += 1
    r -= 1
    if cc=='x' or r>0:
        continue
    fo.append(ind)
    if len(fo)==k:
        break
    r = c+1
r = 0
for ind, cc in enumerate(reversed(s)):
    ind = n-ind
    r -= 1
    if cc=='x' or r>0:
        continue
    ba.append(ind)
    if len(ba)==k:
        break
    r = c+1

for f, b in zip(fo, reversed(ba)):
    if f==b:
        print(f)

Submission status: Accepted

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

# process
l = [i+1 for i in range(N) if S[i] == 'o']
left = [l[0]]
right = [l[-1]]
for i in range(1, len(l)):
    if l[i] > left[-1]+C:
        left.append(l[i])
    if l[-i-1] < right[-1]-C:
        right.append(l[-i-1])

# output
# print(l)
# print(left)
# print(right)
if len(left) == K:
    for i in range(len(left)):
        if left[i] == right[-i-1]:
            print(left[i])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    """
    そもそもK日働くことができるのかは、左から順に働きづめにしてやれば貪欲法で判定できる。
    （必ず働かないといけない日）＝（その日を×にするとK日働けなくなる日）
    なので、O(N^2)でなら愚直な判定が可能。
    これをO(N)に高速化するために、必ず働かないといけないか判定したい日に対してその左右に働ける日が
    何個あるかを求める。
    →そうすると判定したい日を１日ずらしたときに尺取り法のようなことが可能！
    ただし左側の最終日と右側の初日が(C+2)日以下の場合は１日減らさないといけない。
    """

    # 左から貪欲に働く日を数える
    L = []
    work = 0
    diff = C + 1
    for i in range(N):
        if diff > C and S[i] == "o":
            work += 1
            L.append((work, 0))
            diff = 0
        else:
            L.append((work, diff))
        diff += 1
    #print("L={}".format(L))

    # 右から貪欲に働く日を数える
    R = []
    work = 0
    diff = C + 1
    for i in range(1, N + 1):
        if diff > C and S[-i] == "o":
            work += 1
            R.append((work, 0))
            diff = 0
        else:
            R.append((work, diff))
        diff += 1
    R.reverse()
    #print("R={}".format(R))

    # 求積パート
    ans = []

    if N == 1 and S[0] == "o":
        ans.append(1)
    elif N >= 2:
        for i in range(N):
            if S[i] == "x":
                continue
            else:
                if i == 0:
                    total_work = R[1][0]
                elif i == N - 1:
                    total_work = L[N - 2][0]
                else:
                    total_work = L[i - 1][0] + R[i + 1][0]
                    if L[i - 1][1] + R[i + 1][1] + 1 < C:
                        total_work -= 1
                #print("i={}, total_work={}".format(i+1, total_work))
                if total_work < K:
                    ans.append(i + 1)
    for d in ans:
        print(d)
    

if __name__ == "__main__":
    main()