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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,K,C = inputIL()
S = inputS()

L = []

i = 0
c = 0
while i<N:
  if c == K:
    break
  if S[i]=="o":
    L.append(i)
    c += 1
    i += C+1
  else:
    i += 1

R = []

i = N-1
c = 0
while i>=0:
  if c == K:
    break
  if S[i]=="o":
    R.append(i)
    c += 1
    i -= C+1
  else:
    i -= 1

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

left = [0] * N
right = [0] * N

i = 0
cnt = 0
while i < N:
    if cnt == K:
        break
    if S[i] == "o":
        cnt += 1
        left[i] = 1
        i += C + 1
    else:
        i += 1
#print(left)

S = S[::-1]
i = 0
cnt = 0
while i < N:
    if cnt == K:
        break
    if S[i] == "o":
        cnt += 1
        right[i] = 1
        i += C + 1
    else:
        i += 1
right = right[::-1]
#print(right)

left_ls, right_ls = [], []
for i in range(N):
    if left[i]:
        left_ls.append(i + 1)
    if right[i]:
        right_ls.append(i + 1)
        
for l, r in zip(left_ls, right_ls):
    if l == r:
        print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n, k, c = map(int, input().split())
s = input()
a = []
for i in range(n):
    if s[i] == 'o':
        a.append(i+1)

m = len(a)
l = [0 for _ in range(m)]
r = [0 for _ in range(m)]

cur = 0
l[0] = a[0]
while True:
    to = bisect.bisect_left(a, a[cur] + c + 1)
    if to == m:
        break
    l[to] = l[cur] + 1
    cur = to

for i in range(m-1):
    if l[i] > l[i+1]:
        l[i+1] = l[i]

#print(l)

r[m-1] = 1
cur = m-1
while True:
    to = bisect.bisect_left(a, a[cur] - c) - 1
    if to == -1:
        break
    r[to] = r[cur] + 1
    cur = to

for i in range(m-1):
    x = m - 2 - i
    if r[x] < r[x+1]:
        r[x] = r[x+1]

#print(r)
l = [0] + l
r = [r[0]] + r + [0]

for i in range(1, m+1):
    if l[i-1] + r[i+1] < k:
        print(a[i-1])

Submission status: Accepted

Solution code:
line1 = input().split()
n = int(line1[0])
k = int(line1[1])
c = int(line1[2])
s = list(input())
l = [s.index("o") + 1]
r = [len(s) - s[::-1].index("o")]
for i in range(1, k):
  j = l[i - 1]
  m = r[i - 1]
  while j - l[i - 1] <= c or s[j - 1] != "o":
    j += 1
  while r[i - 1] - m <= c or s[m - 1] != "o":
    m -= 1
  r.append(m)
  l.append(j)
r = r[::-1]
for i in range(len(r)):
  if r[i] == l[i]:
    print(r[i])

Submission status: Accepted

Solution code:
def do_solve(n, k, c, s):
    dp = [0 for i in xrange(n)]
    for i in xrange(n):
        dp[i] = 1 if s[i] == 'o' else 0
        if i - c - 1 >= 0:
            dp[i] = max(dp[i], dp[i - c - 1] + 1 if s[i] == 'o' else 0)
        if i - 1 >= 0:
            dp[i] = max(dp[i], dp[i - 1])
    return dp

def solve(n, k, c, s):
    dp1 = do_solve(n, k, c, s)
    dp2 = do_solve(n, k, c, s[::-1])[::-1]

    # print dp1
    # print dp2

    res = []
    for i in xrange(n):
        if s[i] == 'x':
            continue
        l = dp1[i - 1] if i - 1 >= 0 else 0
        r = dp2[i + 1] if i + 1 < n else 0

        # print i, l, r

        if l + r == k - 1:
            res.append(i + 1)
    # print res
    return res

assert solve(16, 4, 3, 'ooxxoxoxxxoxoxxo') == [11, 16]
assert solve(11, 3, 2, 'ooxxxoxxxoo') == [6]
assert solve(5, 1, 0, 'ooooo') == []
assert solve(5, 2, 3, 'ooxoo') == [1, 5]

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

for num in solve(n, k, c, s):
    print num

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, k, c = inpl()
s = list(input())[:-1]
q = collections.deque()
cool = 0
left = [0] * n
right = [0] * n
val=-1
for i in range(n):
    if cool<=0 and s[i]=="o" and val<k:
        val += 1
        cool = c
    else:
        cool-=1
    left[i] = val
cool = 0
val+=1
for i in range(n-1,-1,-1):
    if cool<=0 and s[i]=="o" and val>0:
        val -= 1
        cool = c
    else:
        cool-=1
    right[i]=val
# print(left)
# print(right)
for i in range(n):
    if left[i]==right[i] and (i == 0 or left[i] - left[i - 1] == 1) and (i == n - 1 or right[i + 1] - right[i] == 1):
        print(i + 1)

Submission status: Accepted

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

L=[0]*N
R=[0]*N
c=1
last=-C-1
for i in range(N):
    if i-last>C and S[i]!='x' and c<=K:
        L[i]=c
        c+=1
        last=i
c=K
last=N+C
for i in range(N-1,-1,-1):
    if last-i>C and S[i]!='x' and c>=1:
        R[i]=c
        c-=1
        last=i
for i in range(N):
    if 0<L[i]==R[i]: print(i+1)

Submission status: Accepted

Solution code:

n, k, c = map(int, input().split())
s = input()
l = [0] * k
r = [0] * k
p = 0
# for i in range(n):
i = 0
while i < n:
    if s[i] == "o":
        l[p] = i
        p += 1
        if (p >= k):
            break
        i += c
    i += 1
p = k-1
# for i in range(n - 1, -1, -1):
i = n - 1
while i >= 0:
    if s[i] == "o":
        r[p] = i
        p -= 1
        if (p < 0):
            break
        i -= c
    i -= 1
#print(l, r)
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=input()
INF=float("inf")
left=[0]*(n+1)
right=[0]*(n+1)

mleft=0
last=-c-1
for i in range(n):
    if s[i]=="o" and i-last>c:
        mleft+=1
        last=i
        left[i+1]=mleft

mright=0
last=-c-1
t=s[::-1]
for i in range(n):
    if t[i]=="o" and i-last>c:
        mright+=1
        last=i
        right[i+1]=mright

for i in range(n):
    left[i+1]=max(left[i+1],left[i])
    right[i + 1] = max(right[i + 1], right[i])

left.remove(left[0])
right.remove(right[0])
right=right[::-1]
left.append(0)
right.append(0)

ans=[]
for i in range(1,n+1):
    if s[i-1]=="o":
        if left[i-2]+right[i]<k:
            ans.append(i)


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

Submission status: Accepted

Solution code:
def main():

    N, K, C = [int(i) for i in input().split()]
    S = input().rstrip()

    if all(s == "x" for s in S):
        return
    
    left = [0] * N
    day = 0
    work_cnt = 1
    while day < N:
        if S[day] == "o":
            left[day] = work_cnt
            work_cnt += 1
            day += C
        day += 1
    
    right = [0] * N
    day = N - 1
    work_cnt = K
    while 0 <= day:
        if S[day] == "o":
            right[day] = work_cnt
            work_cnt -= 1
            day -= C
        day -= 1
    
    for i in range(N):
        if left[i] == right[i] and left[i] != 0:
            print(i + 1)

main()

Submission status: Accepted

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

# 前から貪欲に働く日を決めていく。一番早く働く場合
L = []
L_l = 0
off = 0
for i in range(N):
    if S[i] == 'o' and off <= 0:
        L.append(i)
        L_l += 1
        if L_l == K:
            break
        off = C
    else:
        off -= 1

# 後ろから貪欲に働く日を決めていく。一番遅く働く場合
R = []
R_l = 0
off = 0
for i in range(N-1, -1, -1):
    if S[i] == 'o' and off <= 0:
        R.append(i)
        R_l += 1
        if R_l == K:
            break
        off = C
    else:
        off -= 1
R.sort()

# 一番早く働いても遅く働いてもi番目に働く日が同じになる場合、その日は必ず働く必要がある
ans = []
for i in range(K):
    if L[i] == R[i]:
        ans.append(L[i]+1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k,c = map(int, input().split())
    s = input().rstrip()
    left = [0]*n
    day = 0
    temp = 0
    while day < n:
        if s[day] == 'o':
            temp += 1
            left[day] = temp
            for i in range(c):
                if day+i+1 < n:
                    left[day+i+1] = temp
            day += c
        else:
            left[day] = temp
        day += 1

    right = [0]*n
    day = n-1
    temp = 0
    while 0 <= day:
        if s[day] == 'o':
            temp += 1
            right[day] = temp
            for i in range(c):
                if day-i-1 >= 0:
                    right[day-i-1] = temp
            day -= c
        else:
            right[day] = temp
        day -= 1

    res = []
    for i in range(n):
        if s[i] == 'o':
            if i-c-1 < 0:
                pre = 0
            else:
                pre = left[i-c-1]
            if i+c+1 >= n:
                pos = 0
            else:
                pos = right[i+c+1]
            if pre + pos == k-1:
                res.append(i+1)
    for i in range(len(res)):
        if i-1>=0:
            l = res[i-1]
        else:
            l = -1000000
        if i+1<len(res):
            r = res[i+1]
        else:
            r = 10000000
        if res[i]-l>c and r-res[i] > c:
            print(res[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k,c = map(int, input().split())
    s = input().rstrip()
    left = [0]*n
    day = 0
    temp = 1
    while day < n:
        if s[day] == 'o':
            left[day] = temp
            temp += 1
            day += c
        day += 1

    right = [0]*n
    day = n-1
    temp = k
    while 0 <= day:
        if s[day] == 'o':
            right[day] = temp
            temp -= 1
            day -= c
        day -= 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, k, c = inp()
        st = inst()
        front, end = [], []
        def get(now, ans):
            while now < n:
                if len(ans) == k:
                    return
                for i in range(now, n):
                    if st[i]=='o':
                        ans.append(i+1)
                        now = i+c+1
                        break
                else:
                    break
        get(0, front)
        st = st[::-1]
        get(0, end)
        for i in range(len(end)):
            end[i] = n-end[i]+1
        end.sort()
        if len(front)!=k or len(end)!=k:
            return
        ans = []
        # print front, end
        for i in range(k):
            if front[i] == end[i]:
                ans.append(front[i])
        if ans:
            print '\n'.join(map(str, ans))

my_main()

Submission status: Accepted

Solution code:
# with open('./ABC161/max_02') as f:
#     l = [s.strip() for s in f.readlines()]


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

l = list()
r = list()
i = 0
while i < n:
    if len(l) == k:
        break
    if s[i] == 'o':
        l.append(i)
        i += c
    i+=1

i = n-1
while i >= 0:
    if len(r) == k:
        break
    if s[i] == 'o':
        r.append(i)
        i -= c
    i-=1
r.sort()

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

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K, C = getlist()
	S = list(input())
	D1 = defaultdict(int)
	D2 = defaultdict(int)
	var = - float("inf")
	cnt = 0
	for i in range(N):
		if S[i] == "o":
			if i - var >= C + 1:
				cnt += 1
				var = i
				D1[i] += 1

	if cnt >= K + 1:
		return

	#詰める
	var = float("inf")
	cnt = 0
	for i in range(N):
		if S[N - 1 - i] == "o":
			if var - (N - 1 - i) >= C + 1:
				cnt += 1
				var = N - 1 - i
				D2[N - 1 - i] += 1

	# print(D1)
	# print(D2)

	ans = []
	for i in D1:
		if D2[i] == 1:
			ans.append(i)

	ans = sorted(ans)
	for i in ans:
		print(i + 1)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
L = [0]
R = [0]
i = 1
while i <= n:
    if s[i-1] == 'o':
        L.append(i)
        i += c+1
    else:
        i += 1
i = n
while i >= 1:
    if s[i-1] == 'o':
        R.append(i)
        i -= c+1
    else:
        i -= 1
# print(L)
# print(R)
for i in range(1, min(len(L), len(R))):
    if L[i] == R[k-i+1]:
        print(L[i])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import math
import bisect
import re

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

arr1 = [-1] * 200005
arr2 = [-1] * 200005

cnt = 1
day = 0
while day<len(s):
    if s[day] == 'o':
        arr1[day] = cnt
        cnt += 1
        day+=c
    if cnt > k:
        break
    day+=1

cnt = k
day = len(s) - 1
while day>=0:
    if s[day] == 'o':
        arr2[day]=cnt
        cnt-=1
        day-=c
    if cnt <= 0:
        break
    day-=1

for i in range(len(s)):
    if arr1[i]==arr2[i] and arr1[i]!=-1:
        stdout.writelines('%d\n' % (i+1))

Submission status: Accepted

Solution code:
from collections import deque


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K, C = read_ints()
    S = input().strip()
    earliest = []
    i = 0
    while len(earliest) < K:
        if S[i] == 'o':
            earliest.append(i)
            i += C+1
        else:
            i += 1
    latest = []
    i = N-1
    while len(latest) < K:
        if S[i] == 'o':
            latest.append(i)
            i -= C+1
        else:
            i -= 1
    latest.reverse()
    for i, j in zip(earliest, latest):
        if i == j:
            print(i+1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=str(input())
l=[]
r=[]
cnt=0
for i in range(k):
    if s[cnt]=="o":
        l.append(cnt+1)
        cnt+=c+1
    else:
        while s[cnt]!="o":
            cnt+=1
        l.append(cnt+1)
        cnt+=c+1
cnt=1
for i in range(k):
    if s[-cnt]=="o":
        r.append(n-cnt+1)
        cnt+=c+1
    else:
        while s[-cnt]!="o":
            cnt+=1
        r.append(n-cnt+1)
        cnt+=c+1
r=r[::-1]
for i in range(k):
    if l[i]==r[i]:
        print(l[i])

Submission status: Accepted

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

def get_positions():
    res = []
    i = 0
    while i < N and len(res) < K:
        if S[i] == "o":
            res.append(i)
            i = i + C + 1
        else:
            i += 1
    return res

l = get_positions()
S = S[::-1]
r = get_positions()
for i in range(K):
    r[i] = N - 1 - r[i]
S = S[::-1]

lastl = [-1] * (N + 1)
for i in range(K):
    lastl[l[i] + 1] = i
for i in range(N):
    if lastl[i + 1] == -1:
        lastl[i + 1] = lastl[i]

lastr = [-1] * (N + 1)
for i in range(K):
    lastr[r[i]] = i
for i in range(N-1, -1, -1):
    if lastr[i] == -1:
        lastr[i] = lastr[i + 1]

for i in range(N):
    if S[i] == "x":
        continue
    li = lastl[i]
    ri = lastr[i + 1]
    cnt = 0
    if li != -1:
        cnt += (li + 1)
    if ri != -1:
        cnt += (ri + 1)
    if li != -1 and ri != -1 and r[ri] - l[li] <= C:
        cnt -= 1

    if cnt >= K:
        continue
    print(i + 1)

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()[::-1]
Top = []
Bottom = []
yasumi = 0
ans = []
k = K
for i in range(N):
    if (yasumi == 0) and (S[i] == "o") and (k > 0):
        Bottom.append(N-i)
        yasumi += C
        k -= 1
    elif yasumi > 0:
        yasumi -= 1

S_ = S[::-1]
Bottom.sort()
j = -1
yasumi = 0
for i in range(N):
    if (yasumi == 0) and (S_[i] == "o") and (K > 0):
        j += 1
        yasumi += C
        K -= 1
        if j >= len(Bottom):
            break
        elif Bottom[j] == i+1:
            ans.append(i+1)
    elif yasumi > 0:
        yasumi -= 1

for i in ans:
    print(i)

Submission status: Accepted

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

# 左詰めの働くリスト
l_list = [-1 for i in range(N)]
i = 0
cnt = 0
while(i < N and cnt < K):
	if(S[i] == "o"):
		l_list[i] = cnt
		cnt += 1
		i += C
	i += 1

# 右詰めの働くリスト
r_list = [-1 for i in range(N)]
i = N - 1
cnt = 0
while(i >= 0 and cnt < K):
	if(S[i] == "o"):
		r_list[i] = K-1-cnt
		cnt += 1
		i -= C
	i -= 1

# 両方のリストで一致するマス(日)を出力
for i in range(N):
	if(l_list[i] == -1 or r_list[i] == -1):
		continue
	if(l_list[i] == r_list[i]):
		print(i+1)

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
i=0
d1=[-1]*N
for k in range(K):
    while S[i]=='x' and i<N:
        i+=1
    if i==N:break
    d1[i]=k
    i+=C+1
i=0
d2=[-1]*N
for k in range(K-1,-1,-1):
    while S[N-1-i]=='x' and i<N:
        i+=1
    if i==N:break
    d2[N-1-i]=k
    i+=C+1
print(*[i+1 for i in range(N) if d1[i]==d2[i]>=0],sep='\n')

Submission status: Accepted

Solution code:
n,k,c = map(int, input().split())
s=input()
l=[-1] * k
r=[-1] * k
cnt=0
last=-float("inf")
for i in range(n):
    if last+c < i and s[i] == "o":
        last=i
        l[cnt]=i
        cnt+=1
        if cnt==k:
            break

cnt=0
last=float("inf")
for i in reversed(range(n)):
    if i < last-c and s[i] == "o":
        last=i
        r[cnt]=i
        cnt+=1
        if cnt==k:
            break

r=list(reversed(r))
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=input()

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

usirokara=[]
j=N
cnt=0
while j>=1 and cnt<K:
    if S[j-1]=='o':
        usirokara.append(j)
        j-=C+1
        cnt+=1
    else: j-=1
usirokara=usirokara[::-1]

for i in range(K):
    if maekara[i]==usirokara[i]:
        print(maekara[i])

Submission status: Accepted

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

s = input()

L = []
R = []

i = 0
j = n-1



while i<n and len(L)<k :
    if s[i] == "o" :
        L.append(i)
        i += c
    i += 1

while j>-1 and len(R)<k :
    if s[j] == "o" :
        R.append(j)
        j -= c
    j -= 1

R.reverse()

for x in range(k):
    if R[x] == L[x]:
        print(R[x]+1)

Submission status: Accepted

Solution code:

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

  l = []
  r = []

  for i, char in enumerate(s):
    if len(l) >= k:
      break

    if char == 'o' and (not len(l) or i - l[-1] > c):
      l.append(i)

  for i, char in reversed(tuple(enumerate(s))):
    if len(r) >= k:
      break

    if char == 'o' and (not len(r) or r[-1] - i > c):
      r.append(i)

  r.reverse()

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


main()

Submission status: Accepted

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

L = []  # i+1日目に働くのはL[i]日目以降
R = []  # i+1日目に働くのはL[i]日目以前

for i in range(N):
    if len(L) >= K:
        break
    if s[i] == 'o' and (L == [] or (i + 1) - L[-1] > C):
        # 出勤可能('o') 且 (Lが空又はi日目時点の最終出勤からc日経過)
        # ならばLにi+1を追加
        L.append(i + 1)

for i in range(N - 1, -1, -1):
    if len(R) >= K:
        break
    if s[i] == 'o' and (R == [] or R[-1] - (i + 1) > C):
        R.append(i + 1)

R.reverse()
ans = []

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

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=input()
l,r=[],[]
i=0
while i<n:
    if s[i]=="o":
        l.append(i)
        i+=c+1
    else:
        i+=1
i=n-1
while i>-1:
    if s[i]=="o":
        r.append(i)
        i-=c+1
    else:
        i-=1
l=l[:k]
r=r[:k]
r=r[::-1]
for i in range(k):
    if l[i]==r[i]:
        print(l[i]+1)
#print(l)
#print(r)

Submission status: Accepted

Solution code:

n, k, c = list(map(int, input().split()))
s = input()
l1 = [None] * k
l2 = [None] * k
i = 0
j = 0
while j<k and i<n:
    if s[i]=="o":
        l1[j] = i
        i += (c+1)
        j += 1
    else:
        i += 1
i = n-1
j = k-1
while j>=0 and i>=0:
    if s[i]=="o":
        l2[j] = i
        i -= (c+1)
        j -= 1
    else:
        i -= 1
for item1, item2 in zip(l1, l2):
    if item1==item2:
        print(item1+1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k, c = map(int, input().split())
S = [1 if a == "o" else 0 for a in input()]
count = 0
X = [0] * n
Y = [0] * n
i = 0
while i < n:
    if S[i]:
        count += 1
        X[i] = 1
        i += c + 1
    else:
        i += 1
if count > k:
    exit()
i = n - 1
while i >= 0:
    if S[i]:
        Y[i] = 1
        i -= c + 1
    else:
        i -= 1
for i in range(0, n):
    if X[i] and Y[i]:
        print(i + 1)

Submission status: Accepted

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

L = []###i+1回目に働くのはL[i]日目以降
R = []###i+1回目に働くのはL[i]日目以前

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

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

R.reverse()###Rは逆順にappendしたのでreverse
ans = []

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


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

Submission status: Accepted

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

count = 0

l, r = [], []

for i in range(n):
    m = i + c * count
    if m >= n:
        break
    if s[m] == 'o':
        count += 1
        if count > k:
            break
        l.append(m)

count = 0

for i in range(n - 1, -1, -1):
    m = i - c * count
    if m < 0:
        break
    if s[m] == 'o':
        count += 1
        if count > k:
            break
        r.append(m)

l.sort()
r.sort()

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

Submission status: Accepted

Solution code:
# n : 全日数　k：働く日数　c：働いた日からその後働かない日数
n, k, c = map(int, input().split())
s = input()

## 前から貪欲的に働く日を求める l
l = []
i = 0
num = 0
while num < k:
    if s[i] == 'o':
        l.append(i)
        num += 1
        i += c + 1
    else:
        i += 1

## 後ろから貪欲的に働く日を求める r
r = []
num = 0
i = n - 1
while num < k:
    if s[i] == 'o':
        r.append(i)
        num += 1
        i -= c + 1
    else:
        i -= 1
r.reverse()

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

Submission status: Accepted

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

# N:全日数 K:働く日数 C:働いた日からその後働かない日数
N, K, C = map(int, input().split())
S = input()

# num回目に働く日はl[num-1]日目以降
l = []
num = 0
i = 0
while num < K:
    if S[i] == "o":
        l.append(i)
        num += 1
        i += C + 1
    else:
        i += 1

# num回目に働く日はl[num-1]日目以前
r = []
num = 0
i = N - 1
while num < K:
    if S[i] == "o":
        r.append(i)
        num += 1
        i -= C + 1
    else:
        i -= 1
r.reverse()

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()) ; c+=1
s=input()
A=[i+1 for i in range(n) if s[i]=="o"] #働ける日付
L=[1 for i in range(k)] #働く日数[l] はL[l]以降
R=[n for i in range(k)] #L[l]以前

import bisect
for i in range(1,k):
  L[i]= A[bisect.bisect_left(A,L[i-1]+c)]
  R[-i-1]= A[bisect.bisect_right(A,R[-i]-c)-1]

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

Submission status: Accepted

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

# num 回目に働く日は l[num-1] 日目以降
l = []
num = 0 # num = len(l)
i = 0
while num < k:
    if s[i] == 'o':
        l.append(i)
        num += 1
        i += c + 1
    else:
        i += 1

# num 回目に働く日は l[num-1] 日目以前
r = []
num = 0 # num = len(r)
i = n - 1
while num < k:
    if s[i] == 'o':
        r.append(i)
        num += 1
        i -= c + 1
    else:
        i -= 1
r.reverse()

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=input()
l=len(s)
cand=[]
for i in range(l):
    if s[i]=='o':
        cand.append(i+1)
cnt1=[0]*(n+c+2)
cnt2=[0]*(n+c+2)        

for i in range(l):
    if s[i]=='o':
        cnt1[i+1]=max(cnt1[i],cnt1[i-c]+1)
    else:
        cnt1[i+1]=cnt1[i]
for i in range(l-1,-1,-1):
    if s[i]=='o':
        cnt2[i+1]=max(cnt2[i+2],cnt2[i+c+2]+1)
    else:
        cnt2[i+1]=cnt2[i+2]
ans=[]
for i in range(len(cand)):##嘘に見える
    tmp=cand[i]
    if cnt1[tmp-1]+cnt2[tmp+1]<k:
        print(tmp)

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = list(input())
F = []
maru = 0
last = -10**9
span = C
for i in range(N):
    if S[i]=="o" and span >= C:
        maru += 1
        last = i
        F.append([maru,last])
        span = 0
    else:
        span += 1
        F.append([maru,last])
#print(F)
s = S[::-1]
maru = 0
last = 10**9
span = C
E = []
for i in range(N):
    if s[i] == "o" and span >= C:
        maru += 1
        last = N-1-i
        E.append([maru,last])
        span = 0
    else:
        E.append([maru,last])
        span += 1
E = E[::-1]
#print(E)
F = [[0,-10**9]] + F + [[0,10**9]]
E = [[0,-10**9]] + E + [[0,10**9]]
#print(F)
#print(E)
ans = []
for i in range(1,N+1):
    cnt = F[i-1][0] + E[i+1][0]
    
    if S[i-1] == "o":
        if E[i+1][1] - F[i-1][1] < C:
            cnt -= 1
        if cnt == K-1:
            ans.append(i)
    #print(F[i-1],E[i+1],cnt)
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

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

i=0
while i<N:
    if S[i]=="o":
        R.append(i)
        i+=C+1
    else:
        i+=1
i=N-1
while i>=0:
    if S[i]=="o":
        L.append(i)
        i-=(C+1)
    else:
        i-=1
R=R[:K+1]
L=L[:K+1]
L.reverse()
for i in range(K):
    if R[i]==L[i]:
        print(str(R[i]+1),end=" ")