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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k, c = LI()
s = S()
l = [0] * n
r = [0] * n
a = c
x = 0
for i in range(n):
    a += 1
    if s[i] == 'o' and a > c:
        x += 1
        a = 0
    l[i] = x

l = [0] + l
a = c
x = 0
for j in range(n - 1, -1, -1):
    a += 1
    if s[j] == 'o' and a > c:
        x += 1
        a = 0
    r[j] = x

r = r + [0]
for m in range(n):
    if l[m] + r[m + 1] == k - 1:
        print(m + 1)

Submission status: Accepted

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

i=0
while i<n: # 前から貪欲に働く日を決定している。
    if s[i]=='o':
        L.append(i+1)
        i+=(c+1)
    else:
        i+=1

j=0
s2=s[::-1]
while j<n: # 後ろから貪欲に働く日を決定している。
    if s2[j]=='o':
        R.append(n-j)
        j+=(c+1)
    else:
        j+=1
R=R[::-1]        

if len(L)<=k:
    for p in range(min(len(L),len(R))):
        if L[p]==R[p]:
            print(L[p])

Submission status: Accepted

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

a = [0] * k
b = [0] * k

idx = 0
pause = c
for i in range(n):
  pause += 1
  if plan[i]=='x':
    continue
  if pause>c and idx<k:
    a[idx] = i+1 
    idx += 1
    pause = 0
  
idx = k-1
pause = c
for i in range(n-1, -1, -1):
  pause += 1
  if plan[i]=='x':
    continue
  if pause>c:
    if idx>=0:
      b[idx] = i+1
      idx -= 1
      pause = 0
#print(a)
#print(b)

for i in range(k):
  if a[i]==b[i]:
    print(a[i])

Submission status: Accepted

Solution code:
n,k,c = list(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]:
        count += 1
        front[day]= 1
        day += c+1
    else:
        day += 1
    
s = s[::-1]
day = 0
while day < n:
    if s[day]:
        back[day]= 1
        day += c+1
    else:
        day += 1
back = back[::-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:
def main():
    N, K, C = map(int, input().split())
    S = input()

    # greedy
    head, tail = [-C - 1] * (K + 1), [N + C + 1] * (K + 1)
    idx = 0
    for i in range(N):
        if S[i] == 'o' and i - head[idx] > C:
            idx += 1
            head[idx] = i
            if idx == K:
                break
    idx = K
    for i in range(N - 1, -1, -1):
        if S[i] == 'o' and tail[idx] - i > C:
            idx -= 1
            tail[idx] = i
            if idx == 0:
                break
    # ans
    for i in range(K):
        if head[i + 1] == tail[i]:
            print(tail[i] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(s):
  a=[-c]
  for i,s in enumerate(s,1):
    if s<'x'and a[-1]+c<i:a+=i,
  return a[1:k+1]
n,s=open(0)
n,k,c=map(int,n.split())
for a,b in zip(f(s[:n]),f(s[-2::-1])[::-1]):
  if a==n+1-b:print(a)

Submission status: Accepted

Solution code:
Period, WorkingDay, PausePeriod = map(int, input().split())
S = input()
SReverse = S[::-1]

"""
Calculate the day that you can work the fastest and the day that you can work
the slowest. If two days coincide, that day is always a working day.
"""
earliest_days = [-1 for _ in range(Period)]
slowest_days = [-2 for _ in range(Period)]

for days in (earliest_days, slowest_days):
    i_day = 0
    if days == earliest_days:
        i_work_day = 1
        diff_from_next_work = 1
        passion_days = S
    else:
        i_work_day = WorkingDay
        diff_from_next_work = - 1
        passion_days = SReverse
    
    while 1 <= i_work_day and i_work_day <= WorkingDay:
        if passion_days[i_day] == 'o':
            days[i_day] = i_work_day
            i_work_day += diff_from_next_work
            i_day += PausePeriod
        i_day += 1

slowest_days.reverse()
for i_day in range(Period):
    if earliest_days[i_day] == slowest_days[i_day]:
        print(i_day + 1)

exit()

Submission status: Accepted

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

l = []
r = []

res = []


def fun(string, pos):
    counter = 0
    consec_counter = c + 1
    res = []
    while pos < n:
        # print(pos)
        if counter == k:
            break
        if consec_counter >= c and string[pos] == 'o':
            counter += 1
            consec_counter = 0
            res.append(pos)
        else:
            consec_counter += 1
        pos += 1;
    # print(res)
    return res


def invfun(string, pos):
    counter = 0
    consec_counter = c + 1
    res = []
    while pos >= 0:
        if counter == k:
            break
        # print(pos)
        if consec_counter >= c and string[pos] == 'o':
            counter += 1
            consec_counter = 0
            res.append(pos)
        else:
            consec_counter += 1
        pos -= 1;
    # print(res)
    return res


little_res = fun(s, 0)
lres = []
if len(little_res) == k:
    lres = little_res
else:
    exit()

little_res = invfun(s, n - 1)
rres = []
if len(little_res) == k:
    rres = little_res
else:
    exit()
# print(lres)
# print(rres)
for i in range(k):
    if lres[i] == rres[k - 1 - i]:
        print(lres[i] + 1)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=list(input())
p=[-1]*n
i=0
f=0
while i<n:
    if s[i]=='o':
        p[i]=f
        f+=1
        i+=c+1
    else:
        i+=1
i=0
f=0
q=[-1]*n
while i<n:
    if s[n-i-1]=='o':
        q[n-i-1]=f
        f+=1
        i+=c+1
    else:
        i+=1
for i in range(n):
    if p[i]>=0 and q[i]>=0 and p[i]+q[i]==k-1:
        print(i+1)

Submission status: Accepted

Solution code:
INF = 10**18

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

lt = [-INF for _ in range(K + 1)]
rt = [-INF for _ in range(K + 1)]

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[j] == 'o' and j - lt[i - 1] > C:
            lt[i] = j
            break

j = -1
for i in range(1, K + 1):
    while True:
        j += 1
        if S[-1 - j] == 'o' and j - rt[i - 1] > C:
            rt[i] = j
            break

lt = lt[1:]
rt = rt[1:]
rt = [N - x - 1 for x in rt]
rt = rt[::-1]

res = []

for i in range(K):
    if lt[i] == rt[i]:
        res.append(lt[i] + 1)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
n,k,c = list(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]:
    count += 1
    front[day]= 1
    day += c+1
  else:
    day += 1
    
s = s[::-1]
day = 0
while day < n:
  if s[day]:
    back[day]= 1
    day += c+1
  else:
    day += 1
back = back[::-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:
def main():
    N, K, C = map(int, input().split())
    S = input()
    L, R = [-C], [N + C]
    i, k = 0, 0
    while i < N and k < K:
        if S[i] == 'o':
            L.append(i)
            k += 1
            i += C
        i += 1
    L.append(N)
    i, k = N - 1, 0
    while 0 <= i and k < K:
        if S[i] == 'o':
            R.append(i)
            k += 1
            i -= C
        i -= 1
    R.append(N)

    l = 0
    for i, s in enumerate(S):
        if s == 'x':
            continue
        r = K - l
        if R[r] <= i or R[r] - L[l] < C:
            print(i + 1)
        if L[l + 1] == i:
            l += 1


main()

Submission status: Accepted

Solution code:
def with_prev(filt, ad=None):
  prev = None
  def _filt(x):
    nonlocal prev
    if prev is None or filt(x, prev):
      prev = x
      return ad(x) if ad else True
    return False
  return _filt

def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input(), 1) if s=="o"]
  
  if len(workable) == K:
    return workable
  
  filt = with_prev(lambda x,p:p-x>C)
  latest = set(filter(filt, reversed(workable)))

  if len(latest) > K:
    return []
  
  filt = with_prev((lambda x,p:x-p>C), latest.__contains__)
  return filter(filt, workable)

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
def with_prev(filt, prev, ad=None):
  def _filt(x):
    nonlocal prev
    if filt(x, prev):
      prev = x
      return ad(x) if ad else True
    return False
  return _filt

def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input(), 1) if s=="o"]
  
  if len(workable) == K:
    return workable
  
  filt = with_prev((lambda x,p:p-x>C), workable[-1]+C+1)
  latest = set(filter(filt, reversed(workable)))

  if len(latest) > K:
    return []
  
  filt = with_prev((lambda x,p:x-p>C), -C-1, latest.__contains__)
  return filter(filt, workable)

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
# kotae mita
def main():
    N, K, C = map(int, input().split())
    S = input()
    l = [0] * N
    r = [0] * N
    j = K+1
    d = {}
    t = None
    for ii, v in enumerate(reversed(S)):
        i = N - ii - 1
        if v == 'x':
            continue
        if t is None or t - C > i:
            j -= 1
            r[i] = j
            t = i
    if j <= 0:
        return
    t = None
    j = 0
    for i, v in enumerate(S):
        if v == 'x':
            continue
        if t is None or t + C < i:
            j += 1
            l[i] = j
            t = i
    if j > K:
        return
    rr = []
    for i in range(N):
        if r[i] > 0 and r[i] == l[i]:
            rr.append(i+1)
    for i in rr:
        print(i)
main()

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input(), 1) if s=="o"]
  
  if len(workable) == K:
    return workable
  
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
  
  if len(latest) > K:
    return []
  
  def ans():
    prev = -C-1
    for x in workable:
      if x - prev > C:
        if x in latest:
          yield x
        prev = x
  return ans()

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input(), 1) if s=="o"]
  
  if len(workable) == K:
    yield from workable
    return
  
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
  
  if len(latest) > K:
    return
  
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        yield x
      prev = x

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input(), 1) if s=="o"]
  if len(workable) == K:
    return workable
    
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
      if len(latest) > K:
        return []
  must = []
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        must.append(x)
      prev = x
  return must

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i+1 for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
    
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
      if len(latest) > K:
        return []
  must = []
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        must.append(x)
      prev = x
  return must

print("\n".join(map(str, solve())))

Submission status: Accepted

Solution code:
nkc=input().split()
K=int(nkc[1])
C=int(nkc[2])
s=input()
workday_list=[]
for i,youso in enumerate(s) :
  if youso=='o' :
    workday_list.append(i+1)
    

s=1

current_num=0
current_num1=1
list1=[]
list1.append(workday_list[0])
while(s<K) :
  
  if current_num1>=len(workday_list):
    break
  elif workday_list[current_num1]-workday_list[current_num]>C :
    current_num=current_num1
    list1.append(workday_list[current_num1])
    s+=1
  else :
    current_num1=current_num1+1
m=1  

current_num2=len(workday_list)-1
current_num3=len(workday_list)-2
list2=[]
list2.append(workday_list[-1])
while(m<K) :
  
  if current_num3<0:
    break
  elif workday_list[current_num2]-workday_list[current_num3]>C :
    current_num2=current_num3
    list2.append(workday_list[current_num3])
    m+=1
  else :
    current_num3=current_num3-1

list2.reverse()

flag=True
for i in range(len(list1)) :
  if list1[i]==list2[i] :
    flag=False
    print(list1[i])
if flag :
  print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, C, S):
    def f(S):
        r = 0
        w = []
        c = 0
        for s in S:
            if r == 0 and s == 'o':
                w.append(1)
                r = C
                c += 1
            else:
                w.append(0)
                r = max(0, r-1)

        return w
    lw = f(S)
    rw = list(reversed(f(reversed(S))))
    if sum(lw) != K:
        return
    for i, (l, r) in enumerate(zip(lw, rw)):
        if l == r == 1:
            print(i+1)


def main():
    N, K, C = read_int_n()
    S = read_str()
    (slv(N, K, C, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
  
  def to_left():
    prev = workable[-1]+C+1
    for x in reversed(workable):
      if prev - x > C:
        yield x
        prev = x
  latest = set(to_left())
  if len(latest) > K:
    return []
  def to_right():
    prev = -C-1
    for x in workable:
      if x - prev > C:
        if x in latest:
          yield x
        prev = x
  return to_right()

for i in solve():
  print(i+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

to_work_f = set() 
to_work_b = set() 

rest = 0
for i, ch in enumerate(s):
    if rest == 0 and ch == "o":
        to_work_f.add(i)
        rest = c
    elif rest != 0:
        rest -= 1
rest = 0
for i, ch in enumerate(s[::-1]):
    if rest == 0 and ch == "o":
        to_work_b.add(n - i - 1)
        rest = c
    elif rest != 0:
        rest -= 1

if len(to_work_f) > k or len(to_work_b) > k:
    exit()
ans = []
for item in to_work_f:
    if item in to_work_b:
        ans.append(item + 1)
ans.sort()
for item in ans:
    print(item)

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
    
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
  if len(latest) > K:
    return []
  must = []
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        must.append(x)
      prev = x
  return must

for i in solve():
  print(i+1)

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
    
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
      if len(latest) > K:
        return []
  must = []
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        must.append(x)
      prev = x
  return must

for i in solve():
  print(i+1)

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
    
  prev = workable[-1]
  latest = {prev}
  i = len(workable)-1
  while i > 0:
    i -= 1
    if prev - workable[i] > C:
      latest.add(workable[i])
      prev = workable[i]
      if len(latest) > K:
        return []
  must = []
  i = -1
  prev = -C-1
  while i < len(workable)-1:
    i += 1
    if workable[i] - prev > C:
      if workable[i] in latest:
        must.append(workable[i])
      prev = workable[i]
  return must

for i in solve():
  print(i+1)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

l = [0 for i in range(k+1)]
r = [0 for i in range(k+1)]

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

cnt = 0
kaime = k
for j in range(n):
    i = n-1 - j
    if kaime < 1: break
    if cnt > 0:
        cnt -= 1
    else:
        if s[i] == 'o':
            r[kaime] = i
            kaime -= 1
            cnt = c

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

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input().strip()
dp1 = [0]*(N+2)
dp2 = [0]*(N+2)
c = 10*18
cc = 0
for i in range(N):
    if S[i] == "o" and c >= C:
        cc += 1
        c = 0
    else:
        c += 1
    dp1[i+1] = cc
c = 10*18
cc = 0
for i in range(N-1, -1, -1):
    if S[i] == "o" and c >= C:
        cc += 1
        c = 0
    else:
        c += 1
    dp2[i+1] = cc
rs = []
for i in range(N):
    if S[i] == "o" and dp1[i] + dp2[i+2] == K-1 and dp1[i+1] + dp2[i+1] - 1 == K:
        rs.append(i+1)

#print(dp1, dp2)
for r in rs:
    print(r)

Submission status: Accepted

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

latest = [None]*K
i = len(S)+C
for j in range(K-1, -1, -1):
  i = S.rindex("o", 0, i-C)
  latest[j] = i

if i<=C or "o" not in S[:i-C]:
  i = -C-1
  for j in latest:
    i = S.index("o", i+C+1)
    if i == j:
      print(i+1)

Submission status: Accepted

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

latest = [None]*K
i = len(S)+C
for j in range(K):
  i = S.rindex("o", 0, i-C)
  latest[j] = i

if i<=C or "o" not in S[:i-C]:
  i = -C-1
  for j in range(K-1, -1, -1):
    i = S.index("o", i+C+1)
    if i == latest[j]:
      print(i+1)

Submission status: Accepted

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

latest = []
i = len(S)+C
for j in range(K):
  i = S.rindex("o", 0, i-C)
  latest.append(i)

if i<=C or "o" not in S[:i-C]:
  i = -C-1
  for j in range(K):
    i = S.index("o", i+C+1)
    if i == latest.pop():
      print(i+1)

Submission status: Accepted

Solution code:
import sys

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

S=list(input())
if C>=N-1:
    if K==1:
        if S.count("o")>=2:
            sys.exit()
        else:
            print(S.index("o")+1)
            sys.exit()
    else:
        sys.exit()
    
    
left=[0]*N
right=[0]*N

if S[0]=="o":
    left[0]=1
for i in range(1,C+1):
    left[i]=left[i-1]
    if S[i]=="o":
        left[i]=1
for i in range(C+1,N):
    if S[i]=="o":
        left[i]=max(left[i-1],left[i-C-1]+1)
    else:
        left[i]=left[i-1]

if S[-1]=="o":
    right[-1]=1
for i in range(N-2,N-C-2,-1):
    right[i]=right[i+1]
    if S[i]=="o":
        right[i]=1
for i in range(N-C-2,-1,-1):
    if S[i]=="o":
        right[i]=max(right[i+1],right[i+C+1]+1)
    else:
        right[i]=right[i+1]

data=[]
for i in range(N):
    if S[i]=="o":
        L=i-C-1
        R=i+C+1
        num=1
        if L>=0:
            num+=left[L]
        if R<N:
            num+=right[R]
        if num>K:
            sys.exit()
        if num==K:
            data.append(i)

for i in range(len(data)):
    if i==0:
        if data[i+1]-data[i]>C:
            print(data[i]+1)
    elif i==len(data)-1:
        if data[i]-data[i-1]>C:
            print(data[i]+1)
    else:
        if data[i+1]-data[i]>C and data[i]-data[i-1]>C:
            print(data[i]+1)

Submission status: Accepted

Solution code:
N,K,C= map(int, input().split())
S=input()
A=[]
for i in range(N):
  if S[i]=='o':
    A.append(i)
M=[]
d=0
cnt=0
for i in A:
  if d<=i:
    M.append(i)
    d=i+C+1
    cnt+=1
  if cnt==K+1:
    print()
    exit()
    
U=[]
d=N-1
cnt=0
for i in A[::-1]:
  if i<=d:
    U.append(i)
    d=i-C-1
    cnt+=1
  if cnt==K+1:
    print()
    exit()
D=set(M)&set(U)
D=sorted(D)
for i in D:
  print(i+1)

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())
for i in range(n):
	if s[i] == 'o':
		ant = i+1
		antlist = [ant]
		break

for i in range(n):
	if s[n-i-1] == 'o':
		post = n-i
		postlist = [post]
		break

for i in range(k-1):
	ant += c+1
	post -= c+1
	for i in range(n):
		if s[ant+i-1] == 'o':
			ant += i
			antlist.append(ant)
			break
	for i in range(n):
		if s[post-i-1] == 'o':
			post -= i
			postlist.append(post)
			break
postlist.reverse()
#print(antlist)
#print(postlist)
for i in range(k):
	if antlist[i] == postlist[i]:
		print(antlist[i])

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from collections import defaultdict

def resolve():
    N, K, C = iim()
    S = input()

    if C == 0:
        ans = [i+1 for i in range(N) if S[i] == "o"]
        if len(ans) == K:
            print(*ans, sep="\n")
        return

    C1 = C+1
    i, cnt, ax = N-1, 0, [0] * K
    while i >= 0:
        if S[i] != "o":
            i -= 1
        else:
            cnt += 1
            ax[K-cnt] = i
            i -= C1
            if cnt == K:
                break

    ans, cnt, i  = [], 0, 0
    while i < N:
        if S[i] != "o":
            i += 1
        else:
            if i == ax[cnt]:
                ans.append(i+1)
            i += C1
            cnt += 1
            if cnt == K:
                break
    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

# 要素の値は何回目の働く日か(0は働いていない状態)
by_left = [0] * n
by_right = [0] * n

# 左から貪欲
rest = 0
cnt = 1
for itr, s in enumerate(S):
  rest -= 1
  if rest <= 0 and s == "o":
    by_left[itr] = cnt
    cnt += 1
    rest = c + 1
    
# 右から貪欲
rest = 0
cnt = k
for itr, s in enumerate(S[::-1]):
  rest -= 1
  if rest <= 0 and s == "o":
    by_right[n - itr- 1] = cnt
    cnt -= 1
    rest = c + 1

# 左右からの貪欲で、どちらでも同じ働く回数の値が入っている日が必ず働く日
ans = [itr + 1 for itr, (i, j) in enumerate(zip(by_left, by_right)) if i != 0 and i == j]

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from collections import defaultdict

def resolve():
    N, K, C = iim()
    S = input()

    C1 = C+1
    i, cnt, ax = N-1, 0, [0] * K
    while i >= 0:
        if S[i] != "o":
            i -= 1
        else:
            cnt += 1
            ax[K-cnt] = i
            i -= C1
            if cnt == K:
                break

    ans, ri, cnt, i  = [], len(ax)-1, 0, 0
    while i < N:
        if S[i] != "o":
            i += 1
        else:
            if i == ax[cnt]:
                ans.append(i+1)
            i += C1
            cnt += 1
            if cnt == K:
                break
    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
lst = [True] * n
l = []
for i in range(n):
  if s[i] == 'o' and lst[i]:
    l.append(i)
    if len(l) >= k:
      break
    for j in range(c):
      if i + 1 + j < n:
        lst[i+1+j] = False
if len(l) == k:
  lst = [True] * n
  r = []
  for i in range(n - 1, -1, -1):
    if s[i] == 'o' and lst[i]:
      r.append(i)
      if len(r) >= k:
        break
      for j in range(c):
        if i - 1 - j >= 0:
          lst[i-1-j] = False
  if len(r) == k:
    for i in range(k):
      if l[i] == r[k-i-1]:
        print(l[i] + 1)

Submission status: Accepted

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

L = []
R = []
holiday = 0

for i in range(N):
  if holiday:
    holiday -= 1
  elif S[i] == 'o':
    L.append(i)
    holiday = C
holiday = 0
for i in range(N-1, -1, -1):
  if holiday:
    holiday -= 1
  elif S[i] == 'o':
    R.append(i)
    holiday = C
R = R[::-1]
out = set(L) and set(R)
if len(L) == K:
  for l, r in zip(L, R):
    if l == r: print(l+1)

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = list(input())
W = [i for i in range(N) if S[i]=="o" ]
# print(W)

def LR(S,f):
    D = {}
    i = 0
    count = 0
    while i<N and count<K:
        if S[i] == "o":
            count += 1
            if f:
                D[count] = i
            else:
                D[m+1-count] = N-1 - i
            i += C
        i += 1
    return D

L = LR(S,True)
m = max(L)
S.reverse()
R = LR(S,False)
# print(L,R)

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

Submission status: Accepted

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

L = [0 for _ in range(K)]
R = [0 for _ in range(K)]
c = 0
i = 0
while(c < K):
  if S[i] == 'o':
    L[c] = i
    c += 1
    i += C+1
  else:
    i += 1
i = N-1
c = K-1
while(c >= 0):
  if S[i] == 'o':
    R[c] = i
    c -= 1
    i -= C+1
  else:
    i -= 1
#print(L)
#print(R)

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

foward = [0] * (k + 1)
backward = [0] * (k + 1)

# foward check
day = 1
i = 0
while i < n and 0 < day <= k:
    if s[i] == "o":
        foward[day] = i
        i += c
        day += 1
    i += 1

# backward check
day = k
i = n - 1
while 0 <= i and 0 < day <= k:
    if s[i] == "o":
        backward[day] = i
        i -= c
        day -= 1
    i -= 1

for day in range(1, k + 1):
    if foward[day] == backward[day]:
        print(foward[day] + 1)

Submission status: Accepted

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

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

    # 右詰めで働く日
    right = [None for _ in range(len(S))]
    day = K
    i = N
    while i > 0:
        i -= 1

        if S[i] == "x": continue
        right[i] = day
        day -= 1
        if day < 1: break
        i -= C

    # 左詰めで働く日
    left = [None for _ in range(len(S))]
    day = 1  # 働いた日数
    i = -1
    while i < N:
        i += 1

        if S[i] == "x": continue
        left[i] = day

        # 検証
        if left[i] == right[i]:
            print(i+1)

        day += 1
        if day > K: break
        i += C


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

must = set()
i = len(S)+C
for j in range(K):
  i = S.rindex("o", 0, i-C)
  must.add(i)
if i<=C or "o" not in S[:i-C]:
  i = -C-1
  for j in range(K):
    i = S.index("o", i+C+1)
    if i in must:
      print(i+1)