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: Wrong Answer

Solution code:
n,k,c = map(int, input().split())
s = input()
fast = []
pre = -10**10
for i,x in enumerate(s):
    if x == "o" and pre + c < i:
        fast.append(i+1)
        pre = i
    if len(fast) == k:
        break
late = []
pre = -10**10
for i,x in enumerate(s[::-1]):
    if x == "o" and pre + c < i:
        late.append(n-i)
        pre = i
    if len(late) == k:
        break


ans = sorted(list(set(fast) & set(late)))
if len(ans) == 0:
    print()
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
N,K,C = map(int,input().split())
S = input()
dp1 = [0]*N
dp2 = [0]*N

c = 0
if S[0]=='o':
    dp1[0] = 1
    c = C
for i in range(N-1):
    if c==0 and S[i+1]=='o':
        dp1[i+1] = dp1[i]+1
        c = C
    else:
        c = max(0,c-1)
        dp1[i+1] = dp1[i]

c = 0
if S[-1]=='o':
    dp2[-1] = 1
    c = C
for i in range(N-2,-1,-1):
    if c==0 and S[i]=='o':
        dp2[i] = dp2[i+1]+1
        c = C
    else:
        c = max(0,c-1)
        dp2[i] = dp2[i+1]

ans = []
for i in range(N):
    if i==0 or dp1[i]-dp1[i-1]==1:
        if i==N-1 or dp2[i]-dp2[i+1]==1:
            ans.append(i+1)
for i in ans:
    print(i)

Submission status: Wrong Answer

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

dp = [0] * N

dp[N - 1] = 1 if S[N - 1] == "o" else 0
pm = dp[N - 1]
for i in range(N - 2, -1, -1):
    if S[i] == "x" or N - i <= C + 1:
        dp[i] = dp[i + 1]
    else:
        dp[i] = dp[i + C + 1] + 1

# print(dp)
k = K
i = 0
cnt = 0
ans = 0
while i < N:
    if dp[i] < k:
        if cnt == 1:
            print(ans + 1)
        i = max(ans + C + 1, i)
        cnt = 0
        k -= 1
        if k == 0:
            break
    if S[i] == "o" and dp[i] >= k:
        cnt += 1
        if cnt == 1:
            ans = i
    i += 1

if cnt == 1:
    print(ans + 1)

Submission status: Wrong Answer

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

N, K, C = map(int, readline().split())
S = list(readline())
ans = []

def solve(index, K):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

if not (solve(-1, K+1)):
    pass
else:
    index = 0
    while index < N:
        if S[index] == 'x':
            index += 1
        elif solve(index, K):
            ans.append(index + 1)
            index += C + 1
        else:
            index += 1

    for i in ans:
        print(i)

Submission status: Wrong Answer

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

N,K,C = map(int,input().split())
S = input()
#%%
assign_t = [False]*N
assign_b = [False]*N

i = 0
num = 0
while i<N and num<K:
    if S[i]=='o':
        assign_t[i]=True
        num += 1
        i += C+1
    else:
        i += 1
i = N-1
num = 0
while i>=0 and num<K:
    if S[i]=='o':
        assign_b[i]=True
        num += 1
        i -= C+1
    else:
        i -=1

for i in range(N):
    if assign_t[i] and assign_b[i]:
        print(i+1)

Submission status: Wrong Answer

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 f.items():
    if j == 1 and d[i] == 1:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
    n, k, c = [int(x) for x in input().split()]
    s = input()
    can_work = []
    for i, ch in enumerate(s):
        if ch == 'o':
            can_work.append(i)

    if c == 0:
        return

    comb = itertools.combinations(can_work, k)
    appropriate = []
    appropriate_add = appropriate.append
    for v in comb:
        for i, j in enumerate(v[:-1]):
            if v[i + 1] - j <= c:
                break
        else:
            appropriate_add(set(v))
    ans = appropriate[0]
    for ss in appropriate[1:]:
        ans = ans & ss
        # Don't forget +1

    ans = list(ans)
    ans.sort()
    for day in ans:
        print(day + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
N,K,C = map(int,input().split())
S = input()

A = []
for i in range(N):
  if S[i] == 'o':
    A.append(i + 1)
V = 0
for v in itertools.permutations(A, K):
  k = np.array(v[1:])-np.array(v[:-1])
  if all(k > C) == True:
    if V == 0:
      V = set(v)
    else:
      V = V  & set(v)
for i in V:
  print(i)

Submission status: Wrong Answer

Solution code:
import re
import itertools

n, k, c = map(int, input().split())
s = input()
ok_day = [m.start() for m in re.finditer('o', s)]
ok_set = set(itertools.combinations(ok_day, k))
ans = set()
first = True

for i in ok_set:
    min_diff = max(i)
    for t in range(k-1):
        diff = i[t+1] - i[t]
        if diff < min_diff:
            min_diff = diff
    if min_diff >= c + 1:
        if first:
            for u in range(k):
                ans.add(i[u])
            first = False
        else:
            tmp = set()
            for u in range(k):
                tmp.add(i[u])
            tmp_2 = ans & tmp
            ans = set()
            ans = tmp_2

ans_list = list(ans)
for i in ans_list:
    print(i+1)

Submission status: Wrong Answer

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

N,K,C = map(int,input().split())
S = input()
#%%
assign_t = [False]*N
assign_b = [False]*N

i = 0
while i<N:
    if S[i]=='o':
        assign_t[i]=True
        i += C+1
    else:
        i += 1
i = N-1
while i>=0:
    if S[i]=='o':
        assign_b[i]=True
        i -= C+1
    else:
        i -=1

for i in range(N):
    if assign_t[i] and assign_b[i]:
        print(i+1)

Submission status: Wrong Answer

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

chuncks = []
last_workday = -c-10
for i in range(n):
	if s[i] == 'o':
		if len(chuncks) > 0 and i - chuncks[-1][0] <= c:  # in one chunck 
			chuncks[-1].append(i)
		else:
			chuncks.append([i])
		last_workday = i

# print("chuncks before", chuncks)

l = len(chuncks)
if l > k:
	pass
else:
	for i in range(l):
		if i != 0:
			# check with previous
			to_start = 0
			for j in range(len(chuncks[i])):
				if chuncks[i][j] <= chuncks[i-1][0] + c:
					to_start = j+1
			chuncks[i] = chuncks[i][to_start:]

		if i != l-1:
			# check with the next one
			to_finish = len(chuncks[i]) # not inclusive
			for j in range(len(chuncks[i])-1, -1, -1):
				if chuncks[i][j] + c >= chuncks[i+1][-1]:
					to_finish = j
			chuncks[i] = chuncks[i][:to_finish]
		if len(chuncks[i]) == 1:
			print(chuncks[i][0]+1)

# print("chuncks after", chuncks)

Submission status: Wrong Answer

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

dp = [0] * N

dp[N - 1] = 1 if S[N - 1] == "o" else 0
pm = dp[N - 1]
for i in range(N - 2, -1, -1):
    if S[i] == "x" or N - i <= C + 1:
        dp[i] = dp[i + 1]
    else:
        dp[i] = dp[i + C + 1] + 1

# print(dp)
k = K
i = 0
cnt = 0
ans = 0
while i < N:
    if dp[i] < k:
        if cnt == 1:
            print(ans + 1)
            i = ans + C + 1
        cnt = 0
        k -= 1
        if k == 0:
            break
    if S[i] == "o" and dp[i] >= k:
        cnt += 1
        if cnt == 1:
            ans = i
    i += 1

if cnt == 1:
    print(ans + 1)

Submission status: Wrong Answer

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

memo = [0]*N
f = 0
for i in range(N-1, max(-1, N-C-2), -1):
    if S[i] == "o":
        f = 1
        break
if f == 1:
    for i in range(N-1, max(-1, N-C-2), -1):
        memo[i] = 1
for i in range(max(-1, N-C-3), -1, -1):
    if S[i] == "o":
        memo[i] = memo[i+C+1]+1
    else:
        memo[i] = memo[i+1]

m2 = [0]*N
cnt = 0
i = 0
while i < N:
    if S[i] == "o":
        cnt += 1
        m2[i] = cnt
        i += C+1
    else:
        i += 1
m2[0] = (m2[0], 0)
for i in range(1, N):
    if m2[i] == 0:
        m2[i] = m2[i-1]
    else:
        m2[i] = (m2[i], i)

ans = []
for i in range(1, N-1):
    if S[i] == "x":
        continue
    if m2[i-1][1]+C+1 >= N:
        if m2[i-1][0] < K:
            ans.append(i+1)
    elif m2[i-1][0] + memo[max(m2[i-1][1]+C+1, i+1)] < K:
        ans.append(i+1)

if N > 1:
    if m2[-2][0] < K and S[-1] == "o":
        ans.append(N)
    if memo[1] < K and S[0] == "o":
        ans.append(1)
elif S[0] == "o" and K > 0:
    ans.append(1)
ans.sort()
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import itertools
nkc=input().split()
K=int(nkc[1])
C=int(nkc[2])
s=input()
workday_list=[]
for i,youso in enumerate(s) :
  if youso=='o' :
    workday_list.append(i+1)
    
work_candidate=itertools.combinations(workday_list,K)
work_candidate1=[]
for item_list in work_candidate:
  flag=True
  for i in range(len(item_list)-1) :
    if abs(item_list[i]-item_list[i+1])<=C :
      flag=False
      break
  if flag==True :
  	work_candidate1.append(item_list)
list1=set(work_candidate1[0])

for item in work_candidate1 :
  if list1!=set() :
  	list1=set(item) & list1
  else :
    break

for i in list1 :
  print (i)

Submission status: Wrong Answer

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

ans = [0] * n

p = 0
lasto = - c - 1

for i in range(n):
    if p == k:
        break
    if s[i] == "o":
        if i > lasto + c:
            ans[i] += 1
            p += 1
            lasto = i

s = s[::-1]
p = 0
lasto = - c - 1

for i in range(n):
    if p == k:
        break
    if s[i] == "o":
        if i > lasto + c:
            ans[n - 1 - i] += 1
            p += 1
            lasto = i

for i in range(n):
    if ans[i] == 2:
        print(i + 1)

Submission status: Wrong Answer

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

memo = [0]*N
f = 0
for i in range(N-1, max(-1, N-C-2), -1):
    if S[i] == "o":
        f = 1
        break
if f == 1:
    for i in range(N-1, max(-1, N-C-2), -1):
        memo[i] = 1
for i in range(max(-1, N-C-3), -1, -1):
    if S[i] == "o":
        memo[i] = memo[i+C+1]+1
    else:
        memo[i] = memo[i+1]

m2 = [0]*N
cnt = 0
i = 0
while i < N:
    if S[i] == "o":
        cnt += 1
        m2[i] = cnt
        i += C+1
    else:
        i += 1
m2[0] = (m2[0], 0)
for i in range(1, N):
    if m2[i] == 0:
        m2[i] = m2[i-1]
    else:
        m2[i] = (m2[i], i)

ans = []
for i in range(1, N-1):
    if S[i] == "x":
        continue
    if m2[i-1][1]+C+1 >= N:
        if m2[i-1][0] < K:
            ans.append(i+1)
    elif m2[i-1][0] + memo[max(m2[i-1][1]+C+1, i+1)] < K:
        ans.append(i+1)

if N > 1:
    if m2[-2][0] < K:
        ans.append(N)
    if memo[1] < K:
        ans.append(1)
else:
    ans.append(1)
ans.sort()
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n,k,c = map(int, input().split())
s = input()
fast = []
pre = -10**10
for i,x in enumerate(s):
    if x == "o" and pre + c < i:
        fast.append(i+1)
        pre = i
    if len(fast) == k:
        break
late = []
pre = -10**10
for i,x in enumerate(s[::-1]):
    if x == "o" and pre + c < i:
        late.append(n-i)
        pre = i
    if len(late) == k:
        break

late = late[::-1]
ans = sorted(list(set(fast) & set(late)))
for x in ans:
    print(x)

Submission status: Wrong Answer

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

W = [0] * N

if S[0] == o:
  W[0] = 1

for i in range(1, N):
  W[i] = W[i - 1]
  if S[i] == o:
    W[i] += 1

BDP = [0] * N
cnt = 0
if S[0] == o:
  BDP[0] = 1
  cnt = C
for i in range(1, N):
  BDP[i] = BDP[i - 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    BDP[i] += + 1
    cnt = C

ADP = [0] * N
cnt = 0
if S[-1] == o:
  ADP[-1] = 1
  cnt = C
for i in range(N - 2, -1, -1):
  ADP[i] = ADP[i + 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    ADP[i] += 1
    cnt = C

BDP = [0] + BDP

IM = [0] * (N + 2)
ans = 0
for i in range(C):
  if S[i] == x:
    continue
  if ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1
for i in range(C, N - C):
  if S[i] == x:
    continue
  if BDP[i - C] + ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1
for i in range(min(N - C, C), N):
  if S[i] == x:
    continue
  if BDP[i - C] + 1 >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1

for i in range(1, N + 2):
  IM[i] += IM[i - 1]

if BDP[-1] < K:
  exit()

for i in range(1, N + 1):
  if S[i - 1] == o and IM[i] == 0:
    print(i)

Submission status: Wrong Answer

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

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

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    if n == 1:
        return

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None for i in range(n)]
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    go = set()
    back = set()

    i = 0
    while i < n:
        if s[i] == 'o':
            go.add(i)
            if len(go) == k:
                break
            i += c + 1
        else:
            i += 1

    if len(go) < k:
        return

    i = n - 1
    while i >= 0:
        if s[i] == 'o':
            back.add(i)
            if len(back) == k:
                break
            i -= c + 1
        else:
            i -= 1

    if len(back) < k:
        return

    isec = go & back
    print(*map(lambda x: x + 1, isec), sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

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

l = []
for i in range(n):
    if s[i] == "o":
        l.append(i+1)
print(l)

l2 = list(combinations(l, k))
print(l2)

work =[]
for i in range(len(l2)):
    for j in range(k-1):
        if l2[i][j+1] - l2[i][j] <= c:
            break
    else:
        work.append(l2[i])
print(work)

for i in l:
    for j in range(len(work)):
        if i not in work[j]:
            break
    else:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,k,c = l_in()
S = s_in()


i = 0
left = set()

while i < n and len(left) < k:
    if S[i] == 'o':
        left.add(i)
        i += 1+c
    else:
        i += 1

i = n-1
right = set()

while i >= 0 and len(right) < k:
    if S[i] == 'o':
        right.add(i)
        i -= 1+c
    else:
        i -= 1

for i in sorted(list(left.intersection(right))):
    print(i+1)

Submission status: Wrong Answer

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

W = [0] * N

if S[0] == o:
  W[0] = 1

for i in range(1, N):
  W[i] = W[i - 1]
  if S[i] == o:
    W[i] += 1

BDP = [0] * N
cnt = 0
if S[0] == o:
  BDP[0] = 1
  cnt = C
for i in range(1, N):
  BDP[i] = BDP[i - 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    BDP[i] += + 1
    cnt = C

ADP = [0] * N
cnt = 0
if S[-1] == o:
  ADP[-1] = 1
  cnt = C
for i in range(N - 2, -1, -1):
  ADP[i] = ADP[i + 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    ADP[i] += 1
    cnt = C

BDP = [0] + BDP

IM = [0] * (N + 2)
ans = 0
for i in range(C):
  if S[i] == x:
    continue
  if ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1
for i in range(C, N - C):
  if S[i] == x:
    continue
  if BDP[i - C] + ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1
for i in range(min(N - C, C), N):
  if S[i] == x:
    continue
  if BDP[i - C] + 1 >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1

for i in range(1, N + 2):
  IM[i] += IM[i - 1]

if BDP[-1] < K:
  exit()

for i in range(1, N + 1):
  if S[i - 1] == o and IM[i] == 0:
    print(i)

Submission status: Wrong Answer

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

n, k, c = map(int, input().split())
s = input()
m = {}
cnt = 0

def solve(idx, work_days):
    global cnt

    if idx == n:
        # return work_days
        if len(work_days) == k:
            cnt += 1
            for day in work_days:
                if day in m:
                    m[day] += 1
                else:
                    m[day] = 1
        return

    # Cannot work
    if s[idx] == 'x':
        return solve(idx+1, work_days)


    if len(work_days) > 0:
        prevIdx = work_days[-1] - 1
        # TODO: check prev condition
        if idx - prevIdx <= c:
            # cannot work
            solve(idx + 1, work_days)
        else:
            # work
            solve(idx + 1, work_days + [idx + 1])

            # not work
            solve(idx + 1, work_days)
    else:
        # work
        solve(idx+1, work_days + [idx+1])

        # not work
        solve(idx + 1, work_days)

solve(0, [])

# print(cnt, m)
ans = []

for key, val in m.items():
    if val == cnt:
        ans.append(key)

for day in ans:
    print(day)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, k, c = [int(s) for s in input().strip().split()]
    s = input().strip()

    prefix, suffix = [0] * n, [0] * n
    for i in range(n):
        if s[i] == "o":
            prefix[i] = 1 + (prefix[i - c - 1] if i - c - 1 >= 0 else 0)
        else:
            prefix[i] = prefix[i - 1] if i - 1 >= 0 else 0
    for i in range(n - 1, -1, -1):
        if s[i] == "o":
            suffix[i] = 1 + (suffix[i + c + 1] if i + c + 1 < n else 0)
        else:
            suffix[i] = suffix[i + 1] if i + 1 < n else 0
    
    cont = 0
    for i in range(-c + 1, n):
        ok = (prefix[i - 1] if i - 1 >= 0 else 0) + (suffix[i + c] if i + c < n else 0) >= k
        if ok:
            cont = 0
        else:
            cont += 1
            if cont >= c:
                print(i + 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
I = lambda : list(map(int,input().split()))
n,k,m = I();p=0;l=k
s=input();x=set();y=set()
for i in range(n):
    if s[i]=='o' and p==0:
        k-=1;x.add(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
p=0;k=l
for i in range(n-1,-1,-1):
    if s[i]=='o' and p==0:
        k-=1;y.add(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
for i in sorted(x&y):
    print(i)

Submission status: Wrong Answer

Solution code:
I = lambda : list(map(int,input().split()))
n,k,m = I();p=0;l=k
s=input();x=set();y=set()
for i in range(n):
    if s[i]=='o' and p==0:
        k-=1;x.add(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
p=0;k=l
for i in range(n-1,-1,-1):
    if s[i]=='o' and p==0:
        k-=1;y.add(i+1)
        if k==0:
            break
        p=m
    else:
        p-=1;p=max(0,p)
for i in x&y:
    print(i)

Submission status: Wrong Answer

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

W = [0] * N

if S[0] == o:
  W[0] = 1

for i in range(1, N):
  W[i] = W[i - 1]
  if S[i] == o:
    W[i] += 1

BDP = [0] * N
cnt = 0
if S[0] == o:
  BDP[0] = 1
  cnt = C
for i in range(1, N):
  BDP[i] = BDP[i - 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    BDP[i] += + 1
    cnt = C

ADP = [0] * N
cnt = 0
if S[-1] == o:
  ADP[-1] = 1
  cnt = C
for i in range(N - 2, -1, -1):
  ADP[i] = ADP[i + 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    ADP[i] += 1
    cnt = C

BDP = [0] + BDP

IM = [0] * (N + 2)
ans = 0
for i in range(C):
  if S[i] == x:
    continue
  if ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1
for i in range(C, N - C):
  if S[i] == x:
    continue
  if BDP[i - C] + ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1
for i in range(max(N - C, C), N):
  if S[i] == x:
    continue
  if BDP[i - C] + 1 >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C, N) + 1] -= 1

for i in range(1, N + 2):
  IM[i] += IM[i - 1]

for i in range(1, N + 1):
  if S[i - 1] == o and IM[i] == 0:
    print(i)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,c,k = LI()
    s = input()
    k += 1
    dpl = [0]*n
    if s[0] == "o":
        dpl[0] = 1
    else:
        dpl[0] = 0
    for i in range(1,n):
        dpl[i] = dpl[i-1]
        if i >= k and s[i] == "o":
            dpl[i] = max(dpl[i-k]+1,dpl[i])
    dpr = [0]*n
    if s[-1] == "o":
        dpr[-1] = 1
    else:
        dpr[-1] = 0
    for i in range(n-1)[::-1]:
        dpr[i] = dpr[i+1]
        if i < n-k and s[i] == "o":
            dpr[i] = max(dpr[i+k]+1,dpr[i])
    dpl = [0]+dpl
    dpr += [0]
    for i in range(n):
        if dpl[i]+dpr[i+1] < c:
            print(i+1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n,k,c = map(int,input().split())
s = input()
frt = [0]*n
bck = [0]*n
cnt = 0
cntb = 0
prv = 0
prvb = 0
st = set()
stb = set()
for i in range(n):
  if cnt == 0 and s[i] == "o":
    cnt += 1
    frt[i] = 1
    prv = i
    st.add(i)
  elif i-prv > c and s[i] == "o":
    cnt += 1
    frt[i] = cnt
    prv = i
    st.add(i)
for i in range(n)[::-1]:
  if cntb == 0 and s[i] == "o":
    cntb += 1
    bck[i] = 1
    prvb = i
    stb.add(i)
  elif prv-i > c and s[i] == "o":
    cntb += 1
    bck[i] = cntb
    prv = i
    stb.add(i)
ans = []
for i in range(n):
  if i not in st or i not in stb:
    continue
  if frt[i]-1 + bck[i]-1 >= k:
    continue
  print(i+1)

Submission status: Wrong Answer

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

ans = []
cnt = 0
kcn = 0
for i,x in enumerate(s[::-1]):
    i = n - i - 1
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        ans.append(i)
cnt = 0
j = len(ans) - 1
kcn = 0
for i,x in enumerate(s):
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        while 0<=j and ans[j] <= i:
            if ans[j] == i:
                print(i+1)
            j -= 1

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = input()
dp = [0]*(n+1)
nxt = [-1]*n
now = -1
flag = [-1]*n
pre = -c-2
cnt = 0
for i in range(n):
    if s[i] == 'o':
        if now != -1: nxt[now] = i
        now = i
        if pre+c<i and cnt<k:
            pre = i
            flag[i] = cnt
            cnt+=1
dp = [0]*(n+1)
for i in range(n)[::-1]:
    if s[i] == 'x':
        continue
    dp[i] = 1 if i+c+1 >= n else dp[i+c+1]+1
for i in range(n):
    if flag[i] == -1:
        continue
    if flag[i]+dp[nxt[i]]<k:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

def func(Ss):
    dp = [0] * N
    num = 0
    P = 0
    for i, S in enumerate(Ss):
        if P <= 0 and S == 'o':
            num += 1
            P = C
        else:
            P -= 1
        if num > K:
            num = K
        dp[i] = num
    return dp

dp1 = [0] + func(Ss) + [0]
dp2 = [0] + func(Ss[::-1])[::-1] + [0]

#print('dp1:', dp1)
#print('dp2:', dp2)

max12 = max([d1+d2 for d1, d2 in zip(dp1, dp2)])
#print('max12:', max12)

anss = []
for i in range(1, N+1):
    if dp1[i]+dp2[i] != max12:
        continue
    if (dp1[i], dp2[i]) != (dp1[i-1], dp2[i-1]) and (dp1[i], dp2[i]) != (dp1[i+1], dp2[i+1]):
        anss.append(i)

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, K, C = map(int, input().split())
    S = input().rstrip('\n')

    cnt = 0
    c = 0
    rec = {}
    prev = 0
    for i, s in enumerate(S):
        if c:
            c -= 1
            if s == 'o':
                rec[prev].append(i)
            continue
        if s == 'o':
            c = C
            rec[i] = []
            prev = i
            cnt += 1
    if cnt > K:
        exit()
    X = list(rec.keys())
    X.sort()
    ans = []
    prev = 10**9
    for i in range(K-1, -1, -1):
        x = X[i]
        if not rec[x]:
            ans.append(x+1)
            prev = x
            continue
        prev_new = x
        for y in rec[x]:
            if y+C < prev:
                prev_new = y
            else:
                break
        if prev_new == x:
            ans.append(x+1)
        prev = prev_new
    for a in reversed(ans):
        print(a)
    print(rec)


if __name__ == '__main__':
    main()