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()
l = []
tmp = 0
cnt = 0
while (tmp < n):
  if s[tmp] == "o":
    l.append(tmp)
    tmp += c + 1
    cnt += 1
  else:
    tmp += 1
if cnt > k:
  exit()
l2 = []
tmp2 = n - 1
cnt2 = 0
while (tmp2 >= 0):
  if s[tmp2] == "o":
    l2.append(tmp2)
    tmp2 -= c + 1
    cnt2 += 1
  else:
    tmp2 -= 1
if cnt2 > k:
  exit()
for i in range(k):
  if l[i] == l2[k - 1 - i]:
    print(l[i]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,k,c = map(int,input().split())
s = input()
#左右の貪欲 init より大きい点でs[i] == o を探す
l_init = -1
r_init = n
l = []
r = []
# 前から貪欲に探すとl[i] はi+1 回目に働く日の下限である
# 後ろから貪欲に探すとR[i]はk-i 回目に働き日の上限である
# １始まりなので+1 する
for i in range(n):
  if l_init < i and s[i] == "o":
    l.append(i+1)
    l_init = i + c # interval がc 日あるのでi+c 日まで働けない
  j = n-1-i #左からの探索
  if r_init > j and s[j] == "o":
    r.append(j+1)
    r_init = j - c
#print(l[:k],r[len(r)-k:])
# i(1~k)回目に働く時に対して、l[i-1] == r[k-i]かを確かめる
for i in range(1,k+1):
  if l[i-1]  == r[k-i]:
    print(l[i-1])

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k,c = inpm()
    s = list(input())
    circle = []
    for i in range(n):
        if s[i] == 'o':
            circle.append(i)
    pre = -c-10
    cnt = 0
    front = []
    for i in range(len(circle)):
        if pre+c < circle[i]:
            front.append(i)
            pre = circle[i]
            cnt += 1
            if cnt == k:
                break
    pre = n+c+10
    cnt = 0
    back = []
    for i in range(len(circle)-1,-1,-1):
        if pre-c > circle[i]:
            back.append(i)
            pre = circle[i]
            cnt += 1
            if cnt == k:
                break
    back.sort()
    for i in range(k):
        if back[i] == front[i]:
            print(circle[front[i]]+1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説

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

l = [0 for i in range(n)]
r = [-1 for i in range(n)]

a = 1
b = -1
for i in range(n):
    if s[i]=='o' and b<i:
        l[i]=a
        a+=1
        b=i+c
        if a>k:
            break

a = k
b = n
for i in range(n):
    if s[-i-1]=='o' and b>n-i-1:
        r[-i-1]=a
        a-=1
        b=n-i-1-c
        if a<1:
            break

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

Submission status: Accepted

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

l = []
r = []

i = 0
while i<N and len(l)<K:
    if S[i] == 'o':
        l.append(i+1)
        i += C+1
    else:
        i += 1

i = 0
while i<N and len(r)<K:
    if S_reverse[i] == 'o':
        r.append(i)
        i += C+1
    else:
        i += 1

r = [N - i for i in r]
r.reverse()

ans = []

# print(l)
# print(r)

for i in range(K):
    if l[i] == r[i]:
        ans.append(l[i])


# exit()
# ans = set(l) & set(r)

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

L = [0 for _ in range(K+1)]
R = [0 for _ in range(K+1)]

p = 1
i = 1
while i < N+1 and p <= K:
    if S[i] == "o":
        L[p] = i
        i += C
        p += 1
    i += 1

p = K
i = N
while i > 0 and p > 0:
    if S[i] == "o":
        R[p] = i
        i -= C
        p -= 1
    i -= 1

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

Submission status: Accepted

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

L = [0]     # L[i]->前から決めてi回目に働く日
R = []      # R[i]->後ろから決めてi回目に働いていなければいけない日

i = 0
while i < N:
    if S[i] == 'o':
        L.append(i + 1)
        i += C
    i += 1

i = N - 1
while i > -1:
    if S[i] == 'o':
        R.append(i + 1)
        i -= C
    i -= 1
R.append(0)
R.reverse()

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


if min(len(L), len(R)) > K + 1:
    print()
else:
    print('\n'.join([str(a) for a in ans]))

Submission status: Accepted

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

# 計算途中はi=0~n-1日とする

# [a,b] i日までで、限界まで働くとa回働けてb日まで働けない
pre = [[0,0] for i in range(n)]
if s[0]=='o':
    pre[0]=[1,c]
    for j in range(c):
        if 1+j < n:
            pre[1+j] = pre[0] + []

for i in range(1,n):
    if pre[i]==[0,0]:
        if s[i]=='o':
            pre[i][0]=pre[i-1][0]+1
            pre[i][1]+=i+c
            for j in range(c):
                if i+j+1<n:
                    pre[i+j+1]=pre[i]+[]
        else:
            pre[i]=pre[i-1]+[]

# i日以降で限界まで働くとa回働ける
post = [0 for i in range(n)]
if s[-1]=='o':
    post[-1]=1
    for j in range(c):
        if 0 <= n-1-j-1 < n:
            post[-1-j-1] = post[-1]

for i in range(1,n):
    if post[n-i-1]==0:
        if s[n-i-1]=='o':
            post[n-i-1]=post[n-i]+1
            for j in range(c):
                if 0<=n-i-1-j-1<n:
                    post[n-i-1-j-1]=post[n-i-1]
        else:
            post[n-i-1]=post[n-i]

# 0日、n+1日を追加。iを1~n日にする
pre = [[0,0]]+pre+[[0,0]]
post = [0]+post+[0]

# i日に休んだときに、働く回数がkに到達するか調べる
ans = []
for i in range(1,n+1):
    if s[i-1]=='o':
        work, rest = pre[i-1]
        day = min(max(rest,i)+1,n+1)
        work = work + post[day]
        if work<k:
            ans.append(i)

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

n, k, c = nm()
s = ns()
g = [0]*n
f = [0]*n
_h = 0
for i in reversed(range(n)):
    if i + c + 1 < n:
        if _h < g[i+c+1]:
            _h = g[i+c+1]
    if s[i] == 'o':
        g[i] = _h + 1
if max(g) == k:
    _h = 0
    for i in range(n):
        if i > c:
            if _h < f[i-c-1]: _h = f[i-c-1]
        if s[i] == 'o':
            f[i] = _h + 1
    # print(g)
    # print(f)
    a = [0]*(k+2)
    b = [0]*(k+2)
    for i in range(n):
        a[g[i]] = i
    for i in reversed(range(n)):
        b[k+1-f[i]] = i
    # print(a)
    # print(b)
    for i in range(k, 0, -1):
        if a[i] == b[i]:
            print(a[i] + 1)

Submission status: Accepted

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

work_days_early = []
counter = 0
i = 0
while i < N:
    if S[i] == 'o':
        work_days_early.append(i+1)
        counter += 1
        if counter >= K:
            break
        i += C
    i += 1

work_days_late = []
counter = 0
i = N-1
while i >= 0:
    if S[i] == 'o':
        work_days_late.append(i+1)
        counter += 1
        if counter >= K:
            break
        i -= C
    i -= 1
work_days_late.reverse()

work_days_necessary = []
for day1, day2 in zip(work_days_early , work_days_late):
    if day1 == day2:
        work_days_necessary.append(day1)

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

    R = [-1] * k
    L = [-1] * k
    day = INF
    cnt = 0
    for i in range(n):
        if s[i] == 'o':
            if day > c:
                L[cnt] = i
                cnt += 1
                if cnt == k:
                    break
                day = 1
            else:
                day += 1
        else:
            day += 1
    
    day = INF
    cnt = k - 1
    for i in range(n - 1,-1,-1):
        if s[i] == 'o':
            if day > c:
                R[cnt] = i
                cnt -= 1
                if cnt < 0:
                    break
                day = 1
            else:
                day += 1
        else:
            day += 1
    
    ans = []
    for j in range(k):
        if R[j] == L[j]:
            ans.append(R[j] + 1)

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

if __name__ =='__main__':
    main()

Submission status: Accepted

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

l_used = [False]*(n+1)
r_used = [False]*(n+1)
idx = 0
cnt = 0
while idx < n:
    if s[idx] == 'o':
        l_used[idx] = True
        cnt += 1
        idx += c+1
    else:
        idx += 1
idx = n-1
while idx >= 0:
    if s[idx] == 'o':
        r_used[idx] = True
        idx -= c+1
    else:
        idx -= 1

if cnt == k:
    ans = [] 
    for i in range(n):
        if l_used[i] and r_used[i]:
            ans.append(i+1)
    for i in ans:
        print(i)

Submission status: Accepted

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

l = [""] * n
r = [""] * n
x = 1
y = 0
for i in range(n):
    y -= 1
    if s[i] == "o" and y < 0:
        l[i] = x
        x += 1
        y = c
    if x > k:
        x -= 1
        break

y = 0
for i in range(n)[::-1]:
    y -= 1
    if s[i] == "o" and y < 0:
        r[i] = x
        x -= 1
        y = c
    if x <= 0:
        break

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

    cuml = [0] * (n + 1)
    cumr = [0] * (n + 1)
    idx = []

    for i in range(n):
        if s[i] == 'o':
            idx.append(i)
            cuml[i + 1] = cuml[max(i - c,0)] + 1
        else:
            cuml[i + 1] = cuml[i]
    
    for i in range(n - 1,-1,-1):
        if s[i] == 'o':
            cumr[i] = cumr[min(i + c + 1,n)] + 1
        else:
            cumr[i] = cumr[i + 1]
    
    ans = []
    #print(idx,cuml,cumr)
    if c != 0:
        for i in idx:
            flag = False
            for j in range(i - c,i):
                if cuml[max(j + 1,0)] + cumr[min(j + c + 1,n)] >= k:
                    flag = True
                    break

            if flag:
                continue
            else:
                ans.append(i + 1)
    else:
        for i in idx:
            if cuml[i] + cumr[i + 1] < k:
                ans.append(i + 1)
    
    for i in range(len(ans)):
        print(ans[i])
 
if __name__ =='__main__':
    main()

Submission status: Accepted

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

def calc(S):
    now = 1
    ret = [0] * (N + 1)
    while now <= N:
        if S[now] == 'x':
            now += 1
            continue
        ret[now] += 1
        now += C + 1
    for i in range(N):
        ret[i + 1] += ret[i]

    return ret

L = calc('-' + S)
R = calc('-' + S[::-1])[::-1]

ans = []
for mid in range(1, N + 1):
    if S[mid - 1] == 'o' and L[mid] != L[mid - 1] and R[mid] != R[mid - 1] and L[mid] + R[mid] == K:
        ans.append(mid)

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

Submission status: Accepted

Solution code:
import sys

n, k, c = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

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

def main():
    dp_l = make(s)
    dp_r = make(s[::-1])[::-1]

    for i in range(1, n + 1):
        if s[i-1] == 'o':
            if dp_l[i][0] + dp_r[i][0] < k:
                print(i)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
def getWorkDay(S,N,C,K):
    cnt = 0
    day = 0
    flag = False
    L = [0] * N
    for i in range(N):
        if cnt >= K:
            break
        if flag:
            day += 1
            if S[i] == 'o' and day > C:
                cnt += 1
                L[i] = cnt
                day = 0
        else:
            if S[i] == 'o' and day == 0:
                cnt += 1
                L[i] = cnt
                day = 0
                flag = True
    return L

def main():
    N, K, C = map(int, input().split())
    S = list(input())
    L = getWorkDay(S,N,C,K)
    S.reverse()
    R = getWorkDay(S,N,C,K)
    R.reverse()
    cnt = 0
    max_R = max(R)
    for i in range(N-1,-1,-1):
        if R[i]:
            R[i] = max_R - cnt
            cnt += 1

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_e
N, K, C = map(int, input().split())
S = input()

i = 0
left = []
while i < N and len(left) < K:
    if S[i] == 'o':
        left.append(i)
        i += (C + 1)
        continue
    i += 1

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

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, C: int, S: str):
    memo = [-1] * (N + 1)
    def rec(idx):
        if idx >= N:
            idx = N
            memo[idx] = 0
            return memo[idx]
        if memo[idx] >= 0:
            return memo[idx]
        if S[idx] == 'o':
            ret = 1 + rec(idx + C + 1)
        else:
            ret = rec(idx + 1)
        memo[idx] = ret
        return ret

    dp = [0] * (N + 1)
    for i in range(N):
        if memo[i] < 0:
            rec(i)
        dp[i + 1] = max(dp[i + 1], dp[i])
        if S[i] == 'o':
            if i - C < 0:
                tmp = 0
            else:
                tmp = dp[i - C]
            dp[i + 1] = max(dp[i + 1], tmp + 1)
    #print(memo)
    #print(dp)

    ret = []
    for i in range(N):
        if S[i] == 'o' and dp[i] + memo[i + 1] < K:
            ret.append(i + 1)
    if not ret:
        print('')
    for r in ret:
        print(r)
    return

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:
#!/usr/bin/python3


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

#forward pattern
fp = []
idx = 0
while idx < n and len(fp) < k:
    if s[idx] == 'o':
        fp.append(idx + 1)
        idx += c
    idx += 1
    
#reverse pattern
rp = []
idx = n - 1
while 0 <= idx and len(rp) < k:
    if s[idx] == 'o':
        rp.append(idx + 1)
        idx -= c
    idx -= 1

if len(fp) < k or len(rp) < k:
    print('wrong case')
    exit()

fp.sort()
rp.sort()
    
for i in range(k):
    if fp[i] == rp[i]:
        print(fp[i])

Submission status: Accepted

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

A=[]
i=0
while len(A)<K:
  if S[i]=='o':
    A.append(i+1)
    i+=(C+1)
  else:
    i+=1
    
B=[]
i=-1
while len(B)<K:
  if S[i]=='o':
    B.append(i)
    i-=(C+1)
  else:
    i-=1
    
B=[N+i+1 for i in B]
B=B[::-1]
for i in range(K):
  if A[i]==B[i]:
    print(A[i])

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

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

Submission status: Accepted

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

L = [-1] * K
R = [-1] * K
S_index = 0
count = 0
while count < K:
  if S[S_index] == "o":
    L[count] = S_index
    count += 1
    S_index += C+1
  else:
    S_index += 1

S_index = N-1
count = 0
while count < K:
  if S[S_index] == "o":
    R[count] = S_index
    count += 1
    S_index -= C+1
  else:
    S_index -= 1

R.reverse()
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 = input()
p = -C-1
L = []
R = []
for i in range(N):
  if i>p+C and S[i]=='o':
    L.append(i)
    p = i
p = N+C
for i in range(N-1,-1,-1):
  if p>C+i and S[i]=='o':
    R.append(i)
    p = i
R = R[::-1]
if len(L)>K or len(R)>K:
  exit()
ans = []
for a,b in zip(L,R):
  if a==b:
    ans.append(str(a+1))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
#ABC161-E Yutori
"""
左から貪欲に「x回目に働くのはi日目以降」を求め、
右から同じように「x回目に働くのはi日目以前」を求める。
iが一致する場所があれば、そこは必ず働く必要がある。

入力例4では、それぞれ以下のようになる
左：1   2     3    4
　　ooxxoxoxxxoxoxxo
右： 1    2   3    4

よって、11番目の要素と16番目の要素が一致するため答えはこの2つ
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k,c = map(int,readline().split())
s = readline().rstrip().decode('utf-8')

left = [0]*n
right = [-1]*n

i = 0
count = 1
while True:
    if count > k or i >= n:
        break
    if s[i] == "o":
        left[i] = count
        count += 1
        i += c
    i += 1

i = n-1
count = k
while True:
    if count <= 0 or i < 0:
        break
    if s[i] == "o":
        right[i] = count
        count -= 1
        i -= c
    i -= 1

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

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
L, R = [0]*N, [0]*N
i = 0
count = 1
while count <= K:
    if S[i] == 'x':
        i += 1
        continue
    L[i] = count
    count += 1
    i += C+1
i = N-1
count = K
while count > 0:
    if S[i] == 'x':
        i -= 1
        continue
    R[i] = count
    count -= 1
    i -= C+1
for i in range(N):
    if L[i] == 0:
        continue
    if L[i] == R[i]:
        print(i+1)

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)

prev = -10**18
L = []

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

prev = 10**18
R = []

for li in l[::-1]:
    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 = list(map(int, input().split(' ')))
s = input().strip()

froml = list(s)
fromr = list(s)

count = 0
pre = - (c + 1)
for i in range(n):
    if count == k:
        break
    if s[i] == 'o' and i - pre > c:
        froml[i] = str(count)
        pre = i
        count += 1

count = k - 1
pre = n + c
for i in range(n - 1, -1, -1):
    if count < 0:
        break
    if s[i] == 'o' and pre - i > c:
        fromr[i] = str(count)
        pre = i
        count -= 1

for i in range(n):
    if froml[i].isdigit() and froml[i] == fromr[i]:
        print('{} '.format(i + 1))

Submission status: Accepted

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

last=-3000000
l1=[]
l2=set()
for i,c in enumerate(s):
    if last+rest<i and c=="o":
        last=i
        l1.append(i)
last=6000000
for i,c in enumerate(reversed(s)):
    if n-1-i<last-rest and c=="o":
        last=n-1-i
        l2.add(n-1-i)

if len(l1)!=k:
    print()
else:
    for i in l1:
        if i in l2:
            print(i+1)

Submission status: Accepted

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


# 左端から一つ探す。

v=[]
#インデックスを収納
count=0
# 丸からいくら進んだか数えておく。
vc=0
# vの現在の数

for i in range(n):
    if s[i]=='o' and vc==0:
        v.append((i,vc))
        vc+=1
    elif s[i]=='o' and count>=c:
        v.append((i,vc))
        count=0
        vc+=1
    else:
        count+=1

if len(v)>k:
    print('')
    exit()

vc=0
count=0
w=[]
#　右端から探す。
for i in range(n-1,-1,-1):
    if s[i]=='o' and vc==0:
        w.append((i,vc))
        vc+=1
    elif s[i]=='o' and count>=c:
        w.append((i,vc))
        count=0
        vc+=1
    else:
        count+=1
ans=[]
w.sort()
# 共通要素について左右にどれだけ働ける日があるかみる。

for i in range(k):
    if v[i][0]==w[i][0]:
        if v[i][1]+w[i][1]<k:
            ans.append(v[i][0])

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

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #前から見ると最短でできる
    # + 後ろから見ると最遅でできる　→最短でも最遅でも変わらぬ日数で扱うべきなら必須
    N,K,C=MI()
    S=input()
    
    fast=[0]*N
    slow=[0]*N
    inf=10**10
    day=1#何日目にやるか
    i=0
    while i<N:
        if S[i]=="x":
            i+=1
        else:
            fast[i]=day
            day+=1
            i+=C+1
    
    #最遅の場合，後ろから見ているのでdayの順番も逆にしている
    i=N-1
    day=1
    while i>=0:
        if S[i]=="x":
            i-=1
        else:
            slow[i]=day
            day+=1
            i-=C+1
            
            
    ans=[]
    for i in range(N):
        if fast[i]*slow[i]!=0:
            if fast[i]+slow[i]==K+1:
                ans.append(i)
                
                
    for i in range(len(ans)):
        print(ans[i]+1)
            
        
            
            
    
        
    

main()

Submission status: Accepted

Solution code:
def main():
    n,k,c=map(int,input().split())
    s=list(input())
    l,r=[0]*(k+1),[0]*(k+1)
    x,i=1,0
    while i<=n-1:
        if s[i]=='o':
            l[x]=i+1
            i+=c+1
            x+=1
            if x==k+1:
                break
        else:
            i+=1
    x,i=k,n-1
    while 0<=i:
        if s[i]=='o':
            r[x]=i+1
            x-=1
            i-=c+1
            if x==0:
                break
        else:
            i-=1
    for i in range(1,k+1):
        if l[i]==r[i]:
            print(l[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def greedy_count(s):
    global n, c
    res = [0] * (n + 2)
    t = 0
    while t < n:
        if s[t] == "o":
            res[t + 1] = 1
            t += c
        t += 1
    for i in range(n + 1):
        res[i + 1] += res[i]
    return res


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

left = greedy_count(s)
right = greedy_count(s[::-1])[::-1]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

left = [0] * (n + 2)
t = 0
while t < n:
    if s[t] == "o":
        left[t + 1] = 1
        t += c
    t += 1
for i in range(n + 1):
    left[i + 1] += left[i]

right = [0] * (n + 2)
t = n - 1
while t >= 0:
    if s[t] == "o":
        right[t + 1] = 1
        t -= c
    t -= 1
for i in range(n + 1)[::-1]:
    right[i] += right[i + 1]

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

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = list(input())
os = 0
for ss in s:
    if ss == 'o':
        os += 1
s2 = list(reversed(s))

if c == 0 and os > k:
    exit(0)

def calc(s):
    global n, k, c
    answer = set()
    pre = None
    for idx, i in enumerate(s):
        if i == 'o' and (pre is None or idx > pre + c):
            answer.add(idx + 1)
            # 前回働いた日を記録
            pre = idx
        if len(answer) >= k:
            return answer

answer1 = sorted(list(calc(s)))
answer2 = calc(s2)
answer2 = sorted(list(set(map(lambda x: len(s2) - x + 1, answer2))))
# print(answer1)
# print(answer2)

for i in range(len(answer1)):
    if answer1[i] == answer2[i]:
        print(answer1[i])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K,C = LI()
S = list(input())

# oの日
ok = []
for i in range(N):
    if S[i] == 'o':
        ok.append(i)

# 順方向で何日働けるか
dp = [0]*N
dp[0] = 1 if S[0] == 'o' else 0
for i in range(1,N):
    if S[i] == 'o':
        if dp[i-1] == 0:
            dp[i] = 1
        else:
            if i-C-1 >= 0:
                dp[i] = max(dp[i-1],dp[i-C-1]+1)
            else:
                dp[i] = max(dp[i-1],1)
    else:
        dp[i] = dp[i-1]

# 逆方向で何日働けるか
dp2 = [0]*N
dp2[-1] = 1 if S[-1] == 'o' else 0
for i in range(N-1)[::-1]:
    if S[i] == 'o':
        if dp2[i+1] == 0:
            dp2[i] = 1
        else:
            if i+C+1 <= N-1:
                dp2[i] = max(dp2[i+1],dp2[i+C+1]+1)
            else:
                dp2[i] = max(dp2[i+1],1)
    else:
        dp2[i] = dp2[i+1]

# 左右から貪欲をしたときに用いる日
left = []
right = []
now = 0
for i in range(N):
    if dp[i] != now:
        left.append(i)
        now += 1
now = 0
for i in range(N)[::-1]:
    if dp2[i] != now:
        right.append(i)
        now += 1
right = list(reversed(right))

# 次に働ける直近の日
ne = [-1]*N
for i in range(N):
    if S[i] == 'o':
        p = bisect_left(ok,i+C+1)
        if p < len(ok):
            ne[i] = ok[p]

# 次にoが来る日
neo = [-1]*N
for i in range(N):
    if S[i] == 'o':
        p = bisect_left(ok,i+1)
        if p < len(ok):
            neo[i] = ok[p]

ans = []
for i in range(N):
    p1 = bisect_right(left,i-1)-1
    p2 = bisect_left(right,i+1)
    if p1 == -1:
        if p2 == len(right):
            num = 0
        else:
            num = dp2[right[p2]]
    else:
        if p2 == len(right):
            num = dp[left[p1]]
        else:
            v1 = left[p1]
            v2 = right[p2]
            if v1 == v2:
                num = dp[v1]+dp2[v2]-1
            elif v2-v1 >= C+1:
                num = dp[v1]+dp2[v2]
            else:
                nex = ne[v1]
                if nex == -1:
                    num = dp[v1]
                elif nex == i:
                    right = neo[nex]
                    if right == -1:
                        num = dp[v1]
                    else:
                        num = dp[v1]+dp2[right]
                else:
                    num = dp[v1]+dp2[nex]
    if num < K:
        ans.append(i)

for a in ans:
    print(a+1)

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    Q = []
    for i in range(N):
        if S[i] == "o":
            Q.append(i+1)

    forward = []
    day = 0
    cnt = 0
    for q in Q:
        if day < q:
            forward.append(q)
            day = q + C
            cnt += 1
        if cnt == K:
            break
    
    back = []
    day = INF
    cnt = 0
    for q in reversed(Q):
        if q + C < day:
            back.append(q)
            day = q
            cnt += 1
        if cnt == K:
            break
    back.reverse()
    
    for i in range(len(forward)):
        if forward[i] == back[i]:
            print(forward[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)]
now = 1
i = 0
while i < n:
    if s[i] == "o":
        left_to_right[i] = now
        i += c
        now += 1
    i += 1

right_to_left = [0 for _ in range(n)]
now = k
i = n - 1
while 0 <= i:
    if s[i] == "o":
        right_to_left[i] = now
        i -= c
        now -= 1
    i -= 1

for i in range(n):
    if left_to_right[i] == right_to_left[i] and left_to_right[i] != 0:
        print(i + 1)