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()
left = [-1 for _ in range(k)]
right = [-1 for _ in range(k)]

bef = -10 ** 10
cnt = 0
for i, ss in enumerate(s):
    if ss == "o" and i - bef > c:
        if cnt == k:
            exit()
        left[cnt] = i
        bef = i
        cnt += 1

cnt = 0
bef = -10 ** 10
for i, ss in enumerate(s[::-1]):
    if ss == "o" and i - bef > c:
        if cnt == k:
            exit()
        right[k - 1 - cnt] = n - 1 - i
        bef = i
        cnt += 1


for ll, rr in zip(left, right):
    if ll == rr:
        print(ll + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K,C=mi()
    S=list(input())
    ok,ng = "o","x"

    OK = []
    for i in range(N):
        if S[i] == ok:
            OK.append(i+1) # 1-index
    
    greeds = [OK[0]]
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)
            if len(greeds) > K:
                break

    inv_greeds = [OK[-1]]
    inv_OK = OK[::-1]
    for i in range(1,len(OK)):
        x = inv_OK[i]
        if -x + inv_greeds[-1] > C:
            inv_greeds.append(x)
            if len(inv_greeds) > K:
                break
    
    if len(greeds) < K or len(inv_greeds) < K:
        exit()

    greeds = greeds[:K]
    inv_greeds = inv_greeds[:K][::-1]

    # print(greeds,inv_greeds)
    for i in range(len(greeds)):
        if greeds[i] == inv_greeds[i]:
            print(greeds[i])



    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,k,c=MI()
	s=RD()

	A=[]
	now=0

	while now<n and len(A)<k:
		if s[now]=="o":
			A.append(now+1)
			now+=c+1
		else:
			now+=1
	#print(A)

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


	ans=[]
	for i,j in zip(A,B[::-1]):
		if i==j:
			ans.append(i)

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










if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input().rstrip()
P = [0]*(N+1)
cl, l, cr, r = 0, 1, 0, 1
for i in range(N):
    if cl > C and S[i] != "x": cl = 0; l += 1
    cl += 1
    P[i+1] += l
    if cr > C and S[-1-i] != "x": cr = 0; r += 1
    cr += 1
    P[N-2-i] += r
for i in range(N):
    if P[i] < K and S[i] == "o":
        print(i+1)

Submission status: Accepted

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

workL = [0] * (n + 1)
workR = [0] * (n + 1)

cnt = 0
left = 0

while left < n:
    if s[left] == 'o':
        workL[left + 1] += 1
        cnt += 1
        left += c
    left += 1

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

for i in range(n - 1):
    workL[i + 1] += workL[i]
for i in range(n - 1, 0, -1):
    workR[i - 1] += workR[i]


print("\n".join(
    map(str, [i + 1 for i in range(n) if workL[i] + workR[i + 1] < k])))

Submission status: Accepted

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

work_day_min = []
work_day_max = []

for i in range(N):
    if S[i] == 'o':
        if i > 0 and len(work_day_min) > 0:
            if i - work_day_min[-1] <= C:
                continue
        work_day_min.append(i)
    if len(work_day_min) == K:
        break

for i in range(N):
    if S[N - i - 1] == 'o':
        if i > 0 and len(work_day_max) > 0:
            if work_day_max[-1] - (N - i - 1) <= C:
                continue
        work_day_max.append(N - i - 1)
    if len(work_day_max) == K:
        break

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

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
A = []
cnt = 0
for i, s in enumerate(S, 1):
    if cnt > 0:
        cnt -= 1
    elif s == "o":
        cnt = C
        A.append(i)
if len(A) > K:
    exit()
B = []
cnt = 0
for i, s in zip(range(N, 0, -1), S[::-1]):
    if cnt > 0:
        cnt -= 1
    elif s == "o":
        cnt = C
        B.append(i)
assert len(B) == K
B.reverse()
Ans = []
for a, b in zip(A, B):
    if a == b:
        Ans.append(a)
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K, C = LI()
    S = SL()

    L = []
    rest = C
    for i, ch in enumerate(S):
        if ch == "o" and rest >= C:
            rest = -1
            L.append(i)
        rest += 1

    R = []
    rest = C
    for i, ch in list(enumerate(S))[::-1]:
        if ch == "o" and rest >= C:
            rest = -1
            R.append(i)
        rest += 1
        
    for a, b in zip(L[:K], R[:K][::-1]):
        if a == b:
            print(a + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k, c_yutori = tin()
	if n == 1:
		return 1
		
		
	s = input()
	can_work = [0]*n
	can_work[0] = 1 if s[0]=='o' else 0
	yn = c_yutori if s[0]=='o' else 0
	for i, c in enumerate( list(s)[1:],1):
		if yn == 0 and c == 'o':
			can_work[i] = can_work[i-1]+1
			yn = c_yutori
		else:
			can_work[i] = can_work[i-1]
			yn = max(0, yn - 1)
	need_to_work = [k]*n
	if s[-1]=='o':
		need_to_work[-1] = k-1
		yn = c_yutori
	else:
		need_to_work[-1]=k
		yn=0
	for i, c in enumerate(list(s)[-2::-1],1):
		pos = n-i-1
		if yn == 0 and c == 'o':
			need_to_work[pos] = need_to_work[pos+1]-1
			yn = c_yutori
		else:
			need_to_work[pos]=need_to_work[pos+1]
			yn = max(0, yn-1)
	#pa(can_work)
	#pa(need_to_work)
	if need_to_work[1] == 1:
		print(1)
		
	for i in range(1, n-1):
		if can_work[i-1] < need_to_work[i+1]:
			print(i+1)
		
	if can_work[-2]==k-1:
		print(n)
		
		
		
			
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

cand_l = []
cnt = 0
rest = 0
for i in range(N):
    if S[i] == "o" and rest <= 0 and cnt < K:
        cand_l.append(i + 1)
        rest = C
        cnt += 1
    else:
        rest -= 1

cand_r = []
cnt = 0
rest = 0
for i in reversed(range(N)):
    if S[i] == "o" and rest <= 0 and cnt < K:
        cand_r.append(i + 1)
        rest = C
        cnt += 1
    else:
        rest -= 1

for l, r in zip(cand_l, cand_r[::-1]):
    if l == r:
        print(l)

Submission status: Accepted

Solution code:
def solve():
  N, K, C = map(int, input().split())
  S = input()
  l_r,r_l = [0]*N,[0]*N
  i,cnt = 0,0
  while i<N and cnt<K:
    if S[i]=='o':
      l_r[i] = 1
      cnt += 1
      i += C
    i += 1
  j,cnt = N-1,0
  while j>=0 and cnt<K:
    if S[j]=='o':
      r_l[j] = 1
      cnt += 1
      j -= C
    j -= 1
  ans = []
  c_lr = 0
  c_rl = 0
  for i in range(1,N+1):
    if l_r[i-1]:
      c_lr += 1
    if r_l[i-1]:
      c_rl += 1
    if l_r[i-1]*r_l[i-1]==1 and c_lr==c_rl:
      ans.append(i)
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

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

i, cnt = 0, 0
l = []
while cnt < k:
    if s[i] == 'o':
        l.append(i+1)
        cnt += 1
        i += c
    i += 1

i, cnt = n-1, 0
r = []
while cnt < k:
    if s[i] == 'o':
        r.append(i+1)
        cnt += 1
        i -= c
    i -= 1

r.sort()
for i in range(len(r)):
    if l[i] == r[i]:
        print(r[i])

Submission status: Accepted

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

left = []
right = []

i = 0
while i < n:
    if s[i] == 'o':
        left.append(i)
        i += c
        if len(left) == k:
            break
    i += 1
i = n - 1
while i >= 0:
    if s[i] == 'o':
        right.append(i)
        i -= c
        if len(right) == k:
            break
    i -= 1
right.reverse()
ans = []
for i, j in zip(left, right):
    if i == j:
        ans.append(i)
for x in ans:
    print(x + 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)])

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

saisoku = [0] * n
saioso = [0] * n

i = 0
while i < n:
    if s[i] == "x":
        i += 1
        continue
    saisoku[i] = 1
    i += c + 1

if saisoku.count(1) > k:
    exit()

i = n-1
while i >= 0:
    if s[i] == "x":
        i -= 1
        continue
    saioso[i] = 1
    i -= c + 1

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

Submission status: Accepted

Solution code:
def assign(s, n, k, c):
    res = []
    i = 0
    while k > 0 and i < n:
        if s[i] == 'o':
            res.append(i)
            k -= 1
            i += c
        i += 1
    return res


n, k, c = map(int, input().split())
s = input()
a = assign(s, n, k, c)
b = assign(s[::-1], n, k, c)[::-1]
c = [n-x-1 for x in b]

for x, y in zip(a, c):
    if x == y:
        print(x + 1)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


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


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


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')
def main():
	n,k,c=MI()
	s=input().rstrip().decode()
	
	kk=k
	i=0
	L=[]
	while kk:
		if s[i]=="o":
			L.append(i+1)
			i+=c+1
			kk-=1
		else:
			i+=1
		
	kk=k
	i=n-1
	R=[]
	while kk:
		if s[i]=="o":
			R.append(i+1)
			i-=c+1
			kk-=1
		else:
			i-=1
	R.sort()
	
	for i,j in zip(L,R):
		if i==j:
			print(i)
	
	
	
	
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
S = list(input())
L = [0]*k
nx = -1
cnt = 0
for i,s in enumerate(S):
    if i <=nx: continue
    if s =='o':
        L[cnt] = i
        nx = i + c
        cnt += 1
        if cnt ==k: break
R = [0]*k
nx = -1
cnt = 0
for i,s in enumerate(S[::-1]):
    if i <=nx: continue
    if s =='o':
        R[cnt] = n-i-1
        nx = i + c
        cnt += 1
        if cnt ==k: break
for l,r in zip(L,R[::-1]):
    if l ==r:print(l+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K, C = mapint()
S = list(input())
from heapq import heappop, heappush
from itertools import accumulate

Q = []
left = [0]*K
nx = -1
cnt = 0
for i, s in enumerate(S):
    if i<=nx: continue
    if s=='o':
        left[cnt] = i
        nx = i+C
        cnt += 1
        if cnt==K:
            break
right = [0]*K
nx = -1
cnt = 0
for i, s in enumerate(S[::-1]):
    if i<=nx: continue
    if s=='o':
        right[cnt] = N-i-1
        nx = i+C
        cnt += 1
        if cnt==K:
            break

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

Submission status: Accepted

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

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

ind=0
for i in range(N):
  if S[i]=="o":
    if ind>0 and i-L[ind-1]<=C:
      continue
    else:
      L[ind]=i
      ind+=1
  if ind==K:
    break
      
ind=K-1
for i in range(N):
  j = N-1-i
  if S[j]=="o":
    if ind<K-1 and R[ind+1]-j<=C:
      continue
    else:
      R[ind]=j
      ind-=1
  if ind==-1:
    break
ans=[]
for i in range(K):
  if L[i]==R[i]:
    ans.append(L[i]+1)
if not ans:
  exit()

for a in ans:
  print(a)

Submission status: Accepted

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

s = []

count = 0
for i in range(N):
    if len(s) == K:
        break
    if count == 0:
        if S[i] == 'x':
            continue
        else:
            count = C
            s.append(i+1)
    else:
        count -= 1
s2 = []
count = 0
for i in range(N-1, -1, -1):
    if len(s2) == K:
        break
    if count == 0:
        if S[i] == 'x':
            continue
        else:
            s2.append(i+1)
            count = C
    else:
        count -= 1

for a, b in zip(s, s2[::-1]):
    if a == b:
        print(a)

Submission status: Accepted

Solution code:
INF = 1 << 60

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

left = []
b = -INF
cnt1 = 0
for i in range(n):
    if cnt1 == k:
        break
    if s[i] == "x":
        continue
    if b + c < i:
        b = i
        cnt1 += 1
        left.append(i)

right = []
b2 = INF
cnt2 = 0
for i in reversed(range(n)):
    if cnt2 == k:
        break
    if s[i] == "x":
        continue   
    if b2 - c > i:
        b2 = i
        cnt2 += 1
        right.append(i)

right = right[::-1]

# print("right =", right)
# print("left =", left)
m = len(left)
ans = []
for i in range(m):
    if right[i] == left[i]:
        ans.append(right[i])
for i in ans:
    print(i + 1)

Submission status: Accepted

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

L = [] #0index
R = []
now = 0
times = 0
while times < K:
  #print(L)
  if S[now] == "o":
    L.append(now)
    now += C
    times += 1
  now += 1

now = N-1
times = 0
while times < K:
  if S[now] == "o":
    R.append(now)
    now -= C
    times +=1
  now -= 1
R.sort()

#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()
count = 0
day = 0
pre_list = []
while count < K:
    if S[day] == "o":
        pre_list.append(day + 1)
        day += C
        count += 1
    day += 1

count = 0
day = N-1
post_list = []
while count < K:
    if S[day] == "o":
        post_list.append(day+1)
        day -= C
        count += 1
    day -= 1
post_list.reverse()

ans = []
for i in range(K):
    if pre_list[i] == post_list[i]:
        ans.append(pre_list[i])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N,K,C = list(map(int,input().split()))
S = list(input())
L = []
R = []
life = 0
cnt = K
for i in range(N):
    if cnt==0:
        break
    if S[i]=="o":
        if life <= 0:
            life = C
            L.append(i)
            cnt += -1
        else:
            life += -1
    elif S[i]=="x":
        life += -1

life = 0
cnt = K
for i in range(N):
    if cnt==0:
        break
    if S[N-1-i]=="o":
        if life <= 0:
            life = C
            R.append(N-1-i)
            cnt += -1
        else:
            life += -1
    elif S[N-1-i]=="x":
        life += -1

L.sort()
R.sort()
for i in range(min(len(L),len(R))):
    if L[i]==R[i]:
        print(L[i]+1)

Submission status: Accepted

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

    if k > sum(1 for c in s if c == 'o'):
        return

    latest = [None] * k
    earliest = [None] * k
    earliest[0] = s.index('o')
    for i in range(1, k):
        try:
            earliest[i] = s.index('o', earliest[i-1] + c + 1)
        except ValueError:
            return
    
    latest[-1] = s.rindex('o')
    for i in reversed(range(k-1)):
        try:
            latest[i] = s.rindex('o', 0, latest[i+1] - c)
        except ValueError:
            return

    bound_days = [earliest[i] + 1 for i in range(k) if earliest[i] ==
            latest[i]]

    for e, l in zip(earliest, latest):
        if e == l:
            print(e + 1)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k, c = map(int, input().split())
    s = [True if i == 'o' else False for i in input()]
    L = [0]*k
    R = [0]*k
    i = n-1
    now = k-1
    while 0 <= now:
        if s[i]:
            R[now] = i
            i -= c
            now -= 1
        i -= 1
    i = 0
    now = 0
    while now < k:
        if s[i]:
            L[now] = i
            if L[now] == R[now]:
                print(i+1)
            i += c
            now += 1
        i += 1

        



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

work_last=-float("inf")
llist=[]
for i in range(1,N+1):
  if S[i-1]=="o":
    if i-work_last>C:
      llist.append(i)
      work_last=i
  if len(llist)==K:
    break
#print(llist)

work_last=float("inf")
rlist=[]
for i in reversed(range(1,N+1)):
  if S[i-1]=="o":
    if work_last-i>C:
      rlist.append(i)
      work_last=i
  if len(rlist)==K:
    break
rlist.reverse()
#print(rlist)

for i in range(K):
  if llist[i]==rlist[i]:
    print(llist[i])

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k,c = inm()
s = ins()
l = [0]*n
r = [0]*n
for i in range(n):
    if s[i]=='x':
        l[i] = l[max(0,i-1)]
    else:
        l[i] = max(l[max(0,i-1)], (l[i-c-1]+1) if i>c else 1)
for i in range(n-1,-1,-1):
    if s[i]=='x':
        r[i] = r[min(n-1,i+1)]
    else:
        r[i] = max(r[min(n-1,i+1)], (r[i+c+1]+1) if i<n-c-1 else 1)
#ddprint(l)
#ddprint(r)
ans = []
for i in range(n):
    if s[i]=='o' and \
       (l[i-1] if i>0 else 0)+(r[i+1] if i<n-1 else 0)==k-1:
        ans.append(i+1)
for x in ans:
    print(x)

Submission status: Accepted

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

L = [0]*K
R = [0]*K
lpiv = 0
rpiv = N-1
for i in range(K):
    while S[lpiv] == 'x':
        lpiv += 1
    while S[rpiv] == 'x':
        rpiv -= 1
    L[i] = lpiv
    R[i] = rpiv
    lpiv += C+1
    rpiv -= C+1

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

Submission status: Accepted

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

l = [0]*K
i = 0
for j in range(K):
    while S[i] == "x":
        i += 1
    l[j] = i
    i += C+1

r = [0]*K
i = N-1
for j in range(K-1, -1, -1):
    while S[i] == "x":
        i -= 1
    r[j] = i
    i -= C+1
# print(l, r)
[print(l_i+1) for l_i, r_i in zip(l, r) if l_i == r_i]

Submission status: Accepted

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

# もっとも早い日に貪欲に働いたパターン
# もっとも遅い日に貪欲に働いたパターン
# 上記でX回目の仕事が同じ日であればその日は必ず働く必要がある

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

fast = [0] * K
ind = 0
cnt = 0
while cnt < K: # K回働くまで
  if S[ind] == "o":
    fast[cnt] = ind
    cnt += 1
    ind += (C + 1)
  else:
    ind += 1

late = [0] * K
ind = len(S) - 1
cnt = K - 1
while 0 <= cnt:
  if S[ind] == "o":
    late[cnt] = ind
    cnt -= 1
    ind -= (C + 1)
  else:
    ind -= 1
    
ans = []
for i in range(K):
  if fast[i] == late[i]:
    ans += [fast[i] + 1]
    
for a in ans:
  print(a)

Submission status: Accepted

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

# もっとも早い日に貪欲に働いたパターン
# もっとも遅い日に貪欲に働いたパターン
# 上記でX回目の仕事が同じ日であればその日は必ず働く必要がある

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

fast = [0] * K
ind = 0
cnt = 0
while cnt < K: # K回働くまで
  if S[ind] == "o":
    fast[cnt] = ind
    cnt += 1
    ind += (C + 1)
  else:
    ind += 1

late = [0] * K
ind = len(S) - 1
cnt = 0
while cnt < K:
  if S[ind] == "o":
    late[cnt] = ind
    cnt += 1
    ind -= (C + 1)
  else:
    ind -= 1
    
late = late[::-1]

ans = []
for i in range(K):
  if fast[i] == late[i]:
    ans += [fast[i] + 1]
    
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
import heapq
N, K, C = map(int, input().split())
S=list(input())
cnt=0
index=0
dp=[0 for i in range(N)]
while index<N:
    if S[index]=="o":
        cnt+=1
        dp[index]=cnt
        index+=C+1
    else:
        index+=1
for i in range(1,N):
    dp[i]=max(dp[i],dp[i-1])
S=S[::-1]
dp_r=[0 for i in range(N)]
cnt=0
index=0
while index<N:
    if S[index]=="o":
        cnt+=1
        dp_r[index]=cnt
        index+=C+1
    else:
        index+=1
for i in range(1,N):
    dp_r[i]=max(dp_r[i],dp_r[i-1])
dp_r=dp_r[::-1]

ans=[]
S=S[::-1]
for i in range(N):
    if S[i]=="o":
        left=0
        if i-1>=0:
            left=dp[i-1]
        right=0
        if i+1<=N-1:
            right=dp_r[i+1]
        if left+right<K:
            print(i+1)

Submission status: Accepted

Solution code:
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


from collections import defaultdict


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

# dp[i] stores max number of days worked including day i
dp = SegmentTree([0] * N, 0, max)
for i, x in enumerate(S):
    if x == "o":
        dp[i] = max(1, 1 + dp.query(0, max(0, i - C)))


if any(dp[i] > K for i in range(N)):
    # If it's possible to work more than K days, can always skip any day and still work K
    # No output
    print()
    exit()


#print([dp[i] for i in range(N)])


# Clear out day values that can't reach K
inf = float('inf')
dp2 = SegmentTree([0] * N, inf, min)
for i in range(N - 1, -1, -1):
    days = dp[i]
    if days < K and dp2.query(min(N, i + C + 1), N) != days + 1:
        dp2[i] = inf
    else:
        dp2[i] = days


# Any day values that appear only once is critical
groups = defaultdict(list)
for i in range(N):
    days = dp2[i]
    if days != 0:
        groups[days].append(i)

#print([dp2[i] for i in range(N)])
#print(groups)

mustWork = set()
for k, v in groups.items():
    if len(v) == 1:
        mustWork.update(v)

for i in range(N):
    if i in mustWork:
        print(i + 1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
# record positions of included work days for leftmost and rightmost solutions
leftmost_solution = list()
rightmost_solution = list()
timer = -1
for idx in range(n):
  if s[idx] == "o" and timer <= 0:
    leftmost_solution.append(idx)
    if len(leftmost_solution) == k:
      break
    timer = c+1
  timer -= 1
timer = -1
for idx in range(n-1, -1, -1):
  if s[idx] == "o" and timer <= 0:
    rightmost_solution.append(idx)
    if len(rightmost_solution) == k:
      break
    timer = c+1
  timer -= 1
rightmost_solution.reverse()
for left, right in zip(leftmost_solution, rightmost_solution):
  if left == right:
    print(left+1)

Submission status: Accepted

Solution code:

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

    left = [0]*N
    i = 0
    cnt = 1
    while i < N:
        if S[i] == "o":
            left[i] = cnt
            i += C
            cnt += 1
        i += 1

    right = [0]*N
    i = 0
    cnt = K
    T = S[::-1]
    while i < N:
        if T[i] == "o":
            right[i] = cnt
            i += C
            cnt -= 1
        i += 1
    right = right[::-1]

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    def sub(s):
        cur = 0
        last = -(C + 1)
        res = [0] * (N + 1)
        for i in range(N):
            if i - last > C and s[i] == "o":
                cur += 1
                last = i
            res[i + 1] = cur
        return res

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

    left = sub(S)
    T = S[::-1]
    right = sub(T)
    for i in range(N):
        if S[i] == "x":
            continue
        if left[i] + right[N - i - 1] < K:
            print(i + 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

S = "".join(reversed(S))
i = 0
while i < N:
    if S[i] == 'o':
        r.append(N - i)
        i += C + 1
        if len(r) >= K:
            break
    else:
        i += 1

r = list(reversed(r))
# print(l)
# print(r)
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().strip("\n")

L = [-1] * N
R = [10 ** 10] * N

l = 1
r = K
li = 0
ri = N-1
while li < N:
    if S[li] == "o":
        L[li] = l
        l += 1
        li += C + 1
    else: li += 1

while ri >= 0:
    if S[ri] == "o":
        R[ri] = r
        r -= 1
        ri -= C + 1
    else: ri -= 1


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