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 sys
input = sys.stdin.readline

n,k,c = map(int,input().split())
s = list(input())
l1 = []
l2 = []
count = 0
pena = 0
for i in range(n):
    if s[i] == "o":
        if pena == 0:
            count += 1
            pena = c+1
            l1.append(i+1)
    if pena > 0:
        pena -= 1
    if count == k:
        break

pena = count = 0
for i in range(n-1,-1,-1):
    if s[i] == "o":
        if pena == 0:
            count += 1
            pena = c+1
            l2.append(i+1)
    if pena > 0:
        pena -= 1
    if count == k:
        break
l2.sort()

for i,j in zip(l1,l2):
    if i == j:
        print(i)

Submission status: Accepted

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

wd_e = []
wd_l = []

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

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

for a, b in zip(wd_e, wd_l[::-1]):
    if a == b:
        print(a+1)

Submission status: Accepted

Solution code:
import itertools


def main():
    n, k, c = [int(x) for x in input().split()]
    s = input()
    interval = c + 1

    def greedy_working(s):
        i = 0
        li = []
        while len(li) < k:
            if s[i] == 'o':
                li.append(i)
                i += interval
            else:
                i += 1
        return li

    earl = greedy_working(s)
    # 働ける日の文字列を反転すれば後ろから日付を選べる。それをまた反転し，
    # 最終日から引くことで実際の労働日を算出。
    late = [n - d - 1 for d in greedy_working(s[::-1])[::-1]]

    # 最初はsetでやろうとしていた。しかし，最速と最遅の共通の日付を
    # 取るだけだと，何番目の労働日か問わなくなってしまう。
    # ちゃんと1ケースでWAが出る。
    must_work = []
    for i, j in zip(earl, late):
        if i == j:
            must_work.append(i + 1)
    if len(must_work) == 0:
        return
    for i in must_work:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
left_to_right = [0 for _ in range(n)]
right_to_left = [0 for _ in range(n)]

now = 1
i = 0
while i < n:
    if s[i] == "x":
        i += 1
        continue
    left_to_right[i] = now
    now += 1
    i += c + 1
for i in range(1, n):
    if left_to_right[i] == 0:
        left_to_right[i] = left_to_right[i - 1]

s = s[::-1]
now = 1
i = 0
while i < n:
    if s[i] == "x":
        i += 1
        continue
    right_to_left[i] = now
    now += 1
    i += c + 1
right_to_left = right_to_left[::-1]
for i in range(n - 2, -1, -1):
    if right_to_left[i] == 0:
        right_to_left[i] = right_to_left[i + 1]

ans = 0
for i in range(n):
    tmp = 0
    if i - 1 >= 0:
        tmp += left_to_right[i - 1]
    if i + 1 < n:
        tmp += right_to_left[i + 1]
    if tmp < k:
        print(i + 1)

Submission status: Accepted

Solution code:
from collections import deque
n,k,c = map(int,input().split())
s=list(input())
L=deque([])
R=deque([])
i=1
while 0<i<n+1 and len(L)<k:
    if s[i-1]!='x':
        L.append(i)
        i+=c+1
    else:
        i+=1

i=n
while 0<i<n+1 and len(R)<k:
    if s[i-1]!='x':
        R.appendleft(i)
        i-=c+1
    else:
        i-=1
#print(L)
#print(R)

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

Submission status: Accepted

Solution code:
nkc=list(map(int, input().split()))
s=input()
n=nkc[0]
k=nkc[1]
c=nkc[2]
l=[]
r=[]
onum=sum(1 for i in range(len(s)) if s[i]=='o')
num=0
counter=0
while counter<k and num<n:
    #print(num)
    if s[num]=='o':
        l.append(num)
        counter+=1
        num+=c+1
    else:
        num+=1
num=n-1
counter=0
while counter<k and num>=0:
    #print(num)
    if s[num]=='o':
        r.append(num)
        counter+=1
        num-=c+1
    else:
        num-=1
#print(l)
#print(r)
lenr=len(r)
for i in range(min(lenr, len(l))):
    if r[lenr-i-1]==l[i]:
        print(l[i]+1)

Submission status: Accepted

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

def ff(s):
  i = 1
  kin = []
  for k in range(0, K):
    while s[i-1] == "x":
      i = i+1
    kin += [i]
    i = i+C+1
  return( kin )

k1 = ff(S)
S2 = S[::-1]
k2 = ff(S2)
for i in range(0,K):
  k2[i] = N-k2[i]+1
k2 = k2[::-1]

for i in range(0,K):
  if k1[i]==k2[i]:
    print( k1[i] )

Submission status: Accepted

Solution code:
N,K,C= map(int,input().split())
S = input()
T = [n for n, v in enumerate(S) if v == "o"]

a,b=[T[0]],[T[-1]]

for i in range(len(T)):
  if len(a)!=K:
    if T[i]-a[-1]>C:
      a.append(T[i])
  if len(b)!=K:
    if b[-1]-T[-i-1]>C:
      b.append(T[-i-1])
      
for i in range(K):
  if a[i]==b[-i-1]:
    print(a[i]+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

work = [i for i, e in enumerate(s, 1) if e == "o"]
INF = 10 ** 9

work_l = [-INF]
prev = -INF
for e in work:
    if e - prev > c:
        work_l.append(e)
        prev = e

work_r = [INF]
prev = INF
for e in work[::-1]:
    if prev - e > c:
        work_r.append(e)
        prev = e

work_r = work_r[::-1]

ans = []
mx_r = len(work_r)
for e in work:
    l = bisect_left(work_l, e)
    r = bisect_right(work_r, e)
    cnt = (l - 1) + (mx_r - r - 1)
    if work_r[r] - work_l[l-1] <= c:
        cnt -= 1
    if cnt < k:
        ans.append(e)

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

Submission status: Accepted

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

asc = []
desc = [-1 for _ in range(K)]

rest = 0
for day, job in enumerate(S):
    if job == 'o' and rest == 0:
        asc.append(day)
        rest += C+1
    if len(asc) >= K:
        break
    rest = max(0, rest-1)

cursor = K-1
rest = 0
for day, job in reversed(list(enumerate(S))):
    if job == 'o' and rest == 0:
        desc[cursor] = day
        cursor -= 1
        rest += C+1
    if cursor < 0:
        break
    rest = max(0, rest-1)

ans = []
for i in range(K):
    if asc[i] == desc[i]:
        print(asc[i]+1)

Submission status: Accepted

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

work = [i for i, e in enumerate(s, 1) if e == "o"]
l = [0] * (n + 1)
r = [0] * (n + 1)

prev = -INF
cnt = 0
for e in work:
    if e - prev > c:
        cnt += 1
        l[cnt] = e
        prev = e

prev = INF
cnt = 0
for e in work[::-1]:
    if prev - e > c:
        cnt += 1
        r[cnt] = e
        prev = e

l = l[1:k+1]
r = r[1:k+1][::-1]

ans = []
for el, er in zip(l, r):
    if el == er:
        ans.append(el)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

work = [i for i, e in enumerate(s, 1) if e == "o"]
INF = 10 ** 9

work_l = []
prev = -INF
for e in work:
    if e - prev > c:
        work_l.append(e)
        prev = e

work_r = []
prev = INF
for e in work[::-1]:
    if prev - e > c:
        work_r.append(e)
        prev = e

work_r = work_r[::-1]

ans = []
mx_r = len(work_r)
for e in work:
    l = bisect_left(work_l, e)
    r = mx_r - bisect_right(work_r, e)
    if l + r < k:
        ans.append(e)

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

Submission status: Accepted

Solution code:
def work(S, k, c):
    tir = 0
    cnt = 0
    for i, s in enumerate(S):
        if s == 'o' and tir == 0 and cnt < k:
            yield i
            tir = c
            cnt += 1
        else:
            tir = max(tir-1, 0)


n, k, c = map(int, input().split())
S = list(input())
L = [i+1 for i in work(S, k, c)]
R = [n-i for i in work(S[::-1], k, c)][::-1]
for l, r in zip(L, R):
    if l == r:
        print(l)

Submission status: Accepted

Solution code:
# E - Yutori
def find_workdays(
    total_days: int, workdays_length: int, days_off_length: int, schedule: list) -> list:
    if days_off_length == 0:
        workdays = [i for i, can_work in enumerate(schedule, 1) if can_work]
        return workdays if len(workdays) <= workdays_length else []

    workdays_left, workdays_right = [], []

    for workdays, gen in [
        (workdays_left, enumerate(schedule, 1)),
        (workdays_right, ((total_days - i, x) for i, x in enumerate(schedule[::-1]))),
    ]:
        days_off = 0
        for i, can_work in gen:
            if days_off:
                days_off -= 1
                continue
            if can_work:
                workdays.append(i)
                days_off = days_off_length
                if len(workdays) == workdays_length:
                    break

    return [l for l, r in zip(workdays_left, workdays_right[::-1]) if l == r]


def main():
    N, K, C = map(int, input().split())
    S = input().rstrip()
    workdays = find_workdays(N, K, C, [s == "o" for s in S])
    print("\n".join(map(str, workdays)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = input()
def solve():
    l = []
    y = 0
    for i,c in enumerate(S):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            l.append(i+1)
            if len(l) == K:
                break
    r = []
    y = 0
    for i,c in enumerate(S[::-1]):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            r.append(N-i)
            if len(r) == K:
                break
    r.reverse()
    ans = [a for a,b in zip(l,r) if a==b]
    print(*ans, sep='\n')
solve()

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = input()
def solve():
    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()
    l = []
    y = 0
    for i,c in enumerate(S):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            l.append(i+1)
            if len(l) == K:
                break
    r = []
    y = 0
    for i,c in enumerate(S[::-1]):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            r.append(N-i)
            if len(r) == K:
                break
    r.reverse()
    ans = [a for a,b in zip(l,r) if a==b]
    print(*ans, sep='\n')
solve()

Submission status: Accepted

Solution code:
def main():
    n, k, c = map(int, input().split())
    s = list(input())
    right = [False]*n
    left = [False]*n
    nl = [None]*n
    nr = [None]*n
    rp = [-c]*n
    lp = [n+c]*n
    i = 0
    while i < n:
        if s[i] == "o":
            left[i] = True
            i += c+1
        else:
            i += 1
    i = n - 1
    while i >= 0:
        if s[i] == "o":
            right[n-i-1] = True
            i -= c+1
        else:
            i -= 1
    cntl, cntr = 0, 0
    pl, pr = -c, n+c
    for i, (l, r) in enumerate(zip(left, right)):
        nl[i], nr[i]  = cntl, cntr
        lp[i] = pl
        rp[i] = pr
        if l:
            pl = i+1
        if r:
            pr = n-i
        cntl += l
        cntr += r
    for i in range(n):
        if s[i] == "o":
            num = nl[i]+nr[n-i-1]
            if rp[n-i-1]-lp[i] <= c:
                num -= 1
            if num < k:
                print(i+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    L = [-1] * K
    R = [-1] * K

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

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

    ans = (left + 1 for left, right in zip(L, R) if left == right)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def f(S):
    L = []
    on = True
    cnt = 0
    for i in range(n):
        if not on:
            if cnt == c:
                on = True
            cnt += 1
        if on and S[i] == 'o':
            on = False
            cnt = 0
            L.append(i)
            if len(L) == k:
                break
    return L


L = f(S)
R = [n-1-i for i in f(S[::-1])][::-1]
for i in range(k):
    if L[i] == R[i]:
        print(L[i]+1)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

ox = [ c=="o" for c in s ]
work = [False] * (n)
count = 0
prev = -99999999999999
for i,o in enumerate(ox):
    if o:
        if i-prev > c:
            work[i] = True
            prev = i
            count += 1
            if count == k:
                break

# log("ox", ox)
# log("work", work)

kouho = None
last_work = 9999999999999
ans = []
for i in range(n-1, -1, -1):
    if work[i]:
        if kouho == None:
            # log(i, "req")
            ans.append(i+1)
            last_work = i
        else:
            # log(i, "change")
            last_work = kouho
            kouho = None

    if not kouho and ox[i] and last_work-i>c:
        # log(i, "kouho")
        kouho = i

print("\n".join(map(str, sorted(ans))))

Submission status: Accepted

Solution code:
# E - Yutori


def find_workdays(
    total_days: int, workdays_length: int, days_off_length: int, schedule: list
) -> list:
    if days_off_length == 0:
        workdays = [i for i, can_work in enumerate(schedule, 1) if can_work]
        return workdays if len(workdays) <= workdays_length else []

    workdays_left, workdays_right = set(), set()

    for cur_workdays, gen in [
        (workdays_left, enumerate(schedule, 1)),
        (workdays_right, ((total_days - i, x) for i, x in enumerate(schedule[::-1]))),
    ]:
        cur_days_off = 0
        for i, can_work in gen:
            if cur_days_off:
                cur_days_off -= 1
                continue
            if can_work:
                cur_workdays.add(i)
                cur_days_off = days_off_length
                if len(cur_workdays) == workdays_length:
                    break

    return sorted(workdays_left & workdays_right)


def main():
    N, K, C = map(int, input().split())
    S = input().rstrip()
    workdays = find_workdays(N, K, C, [s == "o" for s in S])
    print("\n".join(map(str, workdays)))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(N: int, K: int, C: int, S: str):
    # 最善だったら何ケースか
    work = 0
    rest = 0
    startWork = -1
    leftIndices = set()
    rightIndices = set()
    for i in range(N):
        if S[i] == "o" and rest <= 0:
            rest = C
            work += 1
            leftIndices.add(i)
        else:
            rest -= 1
    if work != K:
        print("")
        exit()
    work = 0
    rest = 0
    for i in range(N-1, -1, -1):
        if S[i] == "o" and rest <= 0:
            rest = C
            work += 1
            rightIndices.add(i)
        else:
            rest -= 1
    for i in sorted(list(leftIndices.intersection(rightIndices))):
        print(i+1)
    # print(rightIndices)
    # rest = -1
    # startWork = -1
    # for i in range(N-1, -1, -1):
    #     if S[i] == "o" and rest <= 0:
    #         rest = C
    #         startWork = i
    #         girigiriIndices.append(i)
    #         print(f"i{i},{rest}")
    #     else:
    #         rest -= 1

    # if work != K:
    #     print("")
    #     # print(work)
    #     exit()
    # for i in girigiriIndices:
    #     print(i+1)
    return


# 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
    solve(N, K, C, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# E - Yutori


def find_workdays(
    total_days: int, workdays_length: int, days_off_length: int, schedule: list
) -> list:
    if days_off_length == 0:
        workdays = [i for i, can_work in enumerate(schedule, 1) if can_work]
        return workdays if len(workdays) <= workdays_length else []

    workdays_left, workdays_right = set(), set()

    cur_days_off = 0
    for i, can_work in enumerate(schedule, 1):
        if cur_days_off:
            cur_days_off -= 1
            continue
        if can_work:
            workdays_left.add(i)
            cur_days_off = days_off_length
            if len(workdays_left) == workdays_length:
                break

    cur_days_off = 0
    for i, can_work in enumerate(schedule[::-1]):
        if cur_days_off:
            cur_days_off -= 1
            continue
        if can_work:
            workdays_right.add(total_days - i)
            cur_days_off = days_off_length
            if len(workdays_right) == workdays_length:
                break

    return sorted(workdays_left & workdays_right)


def main():
    N, K, C = map(int, input().split())
    S = input().rstrip()
    workdays = find_workdays(N, K, C, [s == "o" for s in S])
    print("\n".join(map(str, workdays)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

for i in range(N):
    if S[i]=='o':
        l.append(i)

L = []
prev = -10**18

for li in l:
    if li-prev>C:
        L.append(li)
        prev = li

l = l[::-1]
R = []
prev = 10**18

for li in l:
    if prev-li>C:
        R.append(li)
        prev = li

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

def greedy(A):
    ret = []
    k = i = 0
    while i < N and k < K:
        if A[i] == 'x':
            i += 1
        else:
            ret.append(i)
            k += 1
            i += C+1
    return ret

L = greedy(S)
R = greedy(S[::-1])
R = [N-1-r for r in R][::-1]
for i, l in enumerate(L):
    if R[i] == l:
        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()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(1)
    else:
        t.append(0)

cnt = 0
i = n-1
d = defaultdict(int)
while i >= 0:
    if t[i] == 1:
        cnt += 1
        d[i] = 1
        i -= c+1
        continue
    i -= 1
i = 0
f = defaultdict(int)
while i < n:
    if t[i] == 1:
        f[i] = 1
        i += c+1
        continue
    i += 1
        
if cnt > k:
    print('')
    quit()

lst = []
for i,j in f.items():
    if j == 1 and d[i] == 1:
        lst.append(i+1)
lst.sort()
for i in lst:
    print(i)

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline
N, K, C = map(int, input().split())
S = input().strip()

L, R = [-1]*N, [-1]*N
i = 0
for k in range(K):
  while i < N and S[i] == 'x':
    i += 1
  if i >= N: break
  L[i] = k
  i += C+1
i = N-1
for k in range(K-1, -1, -1):
  while i >= 0 and S[i] == 'x':
    i -= 1
  if i < 0: break
  R[i] = k
  i -= C+1
for i in range(N):
  if L[i] != -1 and L[i] == R[i]:
    print(i+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[i] = tmp
        tmp -= 1
        i -= c
    i -= 1
i = 0
f = defaultdict(int)
tmp = 1
while i < n:
    if s[i] == 'o':
        f[i] = tmp
        tmp += 1
        i += c
    i += 1
for i,j in sorted(f.items()):
    if j == d[i]:
        print(i+1)

Submission status: Accepted

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

def abc161e(n, k, c, s):
    num_cluster_f = 0
    start = []
    cursor = 0
    while cursor < n:
        if s[cursor] == "x":
            cursor += 1
            continue
        else:
            num_cluster_f += 1
            start.append(cursor)
            cursor += c+1

    if k < num_cluster_f:
        return []

    num_cluster_b = 0
    end = []
    cursor = n-1

    while 0 <= cursor:
        if s[cursor] == "x":
            cursor -= 1
            continue
        else:
            num_cluster_b += 1
            end.append(cursor)
            cursor -= c+1

    if k < num_cluster_b:
        return []

    ans = []
    if num_cluster_b < num_cluster_f:
        num_cluster_f = num_cluster_b
    for s, e in zip(start, end[::-1]):
        if s == e:
            ans.append(s+1)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n, k, c = map(int, input().split(" "))
    s = input()
    
    ans = abc161e(n, k, c, s)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
forward=[]
back=[]
ans=[]
tmp=0
for i in range(len(S)):
    if tmp:
        tmp-=1
        continue
    if S[i]=="o":
        forward.append(i+1)
        tmp=C
tmp=0
for i in range(len(S)-1,-1,-1):
    if tmp:
        tmp-=1
        continue
    if S[i]=="o":
        back.append(i+1)
        tmp=C
    if len(back)==K:
        break
back.sort()
for i in range(K):
    if forward[i]==back[i]:
        print(forward[i])

Submission status: Accepted

Solution code:
n,k,c = map(int, input().split())
s = str(input())
t = []
u = []
i,x,y,j = 0,0,0,n-1
while i < n and x < k:
    if s[i] == "o":
        t.append(i)
        x += 1
        i += c
    i += 1
 
while j >= 0 and y < k:
    if s[j] == "o":
        u.append(j)
        y += 1
        j += -c
    j += -1
 
for i in range(0,k):
    if t[i] == u[k-1-i]:
        print(t[i]+1)

Submission status: Accepted

Solution code:
def main():
    n, k, c = map(int, input().split())
    s = input()
    dp = [0]*(n)
    dp2 = [0]*(n+1)
    for i in range(n):
        if i-c-1 < 0:
            dp[i] = 1
        else:
            dp[i] = max(dp[i], dp[i-1])
            if s[i] == "o":
                dp[i] = max(dp[i], dp[i-c-1]+1)
    for i in range(n-1, -1, -1):
        if i+c+1 >= n:
            dp2[i] = 1
        else:
            dp2[i] = max(dp2[i], dp2[i+1])
            if s[i] == "o":
                dp2[i] = max(dp2[i], dp2[i+c+1]+1)
    dp = [0]+dp[:n-1]
    dp2 = dp2[1:]
    dp3 = [dp[i]+dp2[i] for i in range(n)]
    for i in range(n):
        if dp3[i] < k:
            print(i+1)


main()

Submission status: Accepted

Solution code:
n, k, c = map(int,input().split())
s = input()
left = [0 for _ in range(n)]
right = [0 for _ in range(n)]
cnt = 0
i = 0
while i < n:
    if s[i] == 'o':
        cnt += 1
        left[i] = cnt
        i += c
        if cnt == k:
            break
    i += 1

cnt = k+1
i = n-1
while i >= 0:
    if s[i] == 'o':
        cnt -= 1
        right[i] = cnt
        i -= c
        if cnt == 0:
            break
    i -= 1

ans = []
for i in range(n):
    li = left[i]
    ri = right[i]
    if li > 0 and ri > 0 and li == ri:
        ans.append(i+1)
for a in ans:
    print(a)

Submission status: Accepted

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

def yutori(s, inv):
    ans = [0] * k
    index = 0
    for i in range(k):
        if inv:
            ans[(k - 1) - i] = (n - 1) - s.find('o', index)
            index = s.find('o', index) + (c + 1)
        else:
            ans[i] = s.find('o', index)
            index = ans[i] + (c + 1)
    return ans

l = yutori(s, 0)
r = yutori(s[::-1], 1)
for i, j in zip(l, r):
    if i == j:
        print(i + 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K, C = map(int, rl().split())
    S = input()
    
    left_greedy = [False] * N
    right_greedy = [False] * N
    
    i, cnt = 0, 0
    while i < N:
        if S[i] == 'o':
            cnt += 1
            left_greedy[i] = True
            i += C + 1
        else:
            i += 1
    
    if K < cnt:
        exit()
    
    i = N - 1
    while 0 <= i:
        if S[i] == 'o':
            right_greedy[i] = True
            i -= C + 1
        else:
            i -= 1
    
    for i in range(N):
        if left_greedy[i] and right_greedy[i]:
            print(i + 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    def greed(s):
        workday = []
        start = 0
        while start < n:
            if s[start] == 'x':
                start += 1
            else:
                workday.append(start+1)
                start += c + 1
        return workday

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

    front = greed(s)
    back = [n+1-i for i in greed(s[::-1])[::-1]]

    if len(front) > k or len(back) > k:
        return
    for i, j in zip(front, back):
        if i == j:
            print(i)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

left = []
last = -c-1
for i in range(n):
    if s[i] == "o":
        if last + c < i:
            left.append(i)
            last = i
            if len(left) == k:
                break
            
right = []
last = n + c
for i in range(n)[::-1]:
    if s[i] == "o":
        if last - c > i:
            right.append(i)
            last = i
            if len(right) == k:
                break

right = right[::-1]

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

Submission status: Accepted

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

def yutori(s, inv):
    ans = [0] * k
    index = 0
    for i in range(k):
        if inv:
            ans[(k - 1) - i] = (n - 1) - s.find('o', index)
            index = s.find('o', index) + (c + 1)
        else:
            ans[i] = s.find('o', index)
            index = ans[i] + (c + 1)
    return ans

l = yutori(s, 0)
r = yutori(s[::-1], 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 = " " + input()
work_fw = [0]*k
work_bw = [0]*k
i = 1
now_k = 0
while i <= n and now_k < k:
    if s[i] == 'o':
        work_fw[now_k] = i
        now_k += 1
        i += c
    i += 1
if now_k != k:
    print("")
else:
    i = n
    now_k = k - 1
    while i > 0 and now_k >= 0:
        if s[i] == 'o':
            work_bw[now_k] = i
            now_k -= 1
            i -= c
        i -= 1
    # print(work_fw)
    # print(work_bw)
    for i in range(k):
        if work_fw[i] == work_bw[i]:
            print(work_fw[i] )

Submission status: Accepted

Solution code:
def main():
    n, k, c = map(int, input().split())
    s = input().strip()
    front = []
    start = 0
    days = k
    while start < n:
        if s[start] == 'x':
            start += 1
        else:
            front.append(start+1)
            start += c + 1

    if len(front) > k:
        return

    back = []
    start = n-1
    while start >= 0:
        if s[start] == 'x':
            start -= 1
        else:
            back.append(start+1)
            start -= c + 1

    for i, j in zip(front, back[::-1]):
        if i == j:
            print(i)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k,y,c = map( int, input().split(" "))
ss = input()

asc = []
dsc = []

cnt = 0
err_flg = 0
while( True ):
  if(len(ss) <= cnt):
    err_flg = 1
    break
  if( ss[cnt] == "o"):
    asc.append( cnt )
    cnt += c+1
  else:
    cnt += 1
    
  if( len(asc)==y ):
    break

cnt = 0
ss = ss[::-1]
while( True ):
  if(len(ss) <= cnt):
    err_flg = 1
    break
  if( ss[cnt] == "o"):
    dsc.append( cnt )
    cnt += c+1
  else:
    cnt += 1
    
  if( len(dsc)==y ):
    break
    
for i in range(len(dsc)):
  dsc[i] = len(ss) - dsc[i] - 1
  
dsc.reverse()
#print(asc)
#print(dsc)

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

Submission status: Accepted

Solution code:
import sys

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

ini = []
las = []


cnt = C
for c, i in enumerate(S):
    if cnt >= C and i == "o":
        ini.append(c)
        cnt = 0
    else:
        cnt += 1

cnt = C
for c, i in enumerate(reversed(S)):
    if cnt >= C and i == "o":
        las.append(len(S) - c - 1)
        cnt = 0
    else:
        cnt += 1

las = sorted(las)

if len(ini) > K:
    sys.exit()

for i, j in zip(ini, las):
    if i == j:
        print(i+1)