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:
import sys
sys.setrecursionlimit(10000000)

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

must_day = set(list(range(1,n+1)))

def dfs(day, rest, workdays):
  if rest < 1:
    global must_day, kouho_n
    kouho_n += 1
    must_day = must_day & set(workdays)
    return
  elif day > n:
    return
  else:
    if day - workdays[-1] > c and s[day-1] == 'o':
      dfs(day+1, rest-1, workdays+[day])
    dfs(day+1, rest, workdays)
    return
dfs(1, k, [-c])

if kouho_n > 0:
  for d in must_day:
    print(d)

Submission status: Wrong Answer

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

arr = [None] * N
rest = 0
k = K+1
for i in range(N-1, -1, -1):
    if rest > 0:
        rest -= 1
    elif S[i] == 'o':
        k = max(1, k-1)
        rest = C
    arr[i] = k

ct = Counter()
rest = 0
prev = None
for i in range(N):
    if arr[i] != prev and prev is not None:
        if ct[prev] == 1:
            print(i)
            rest = C
    if S[i] == 'o':
        if rest == 0:
            ct[arr[i]] += 1
    rest = 0 if rest == 0 else rest - 1
    prev = arr[i]
if ct[prev] == 1:
    print(i+1)
    rest = C

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;s=s[::-1]
for i in range(n):
    if s[i]=='o' and p==0:
        k-=1;y.add(n-i)
        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:
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
owari = max(dp[i] - k, 0)
while i < N:
    if dp[i] < k:
        # print(i, cnt, ans, k, ans + C + 1)
        if cnt == 1:
            print(ans + 1)
        i = max(ans + C + 1, i)
        ans = 0
        cnt = 0
        k -= 1
        if k == owari:
            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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 前からと後ろからでcandに入れて両方に入るところ
N, K, C = lr()
S = sr()
cand1 = set()
cand2 = set()

def F(S):
    cand = set()
    count = 0
    cur = 0
    while cur < len(S):
        if S[cur] == 'o':
            count += 1
            cand.add(cur)
            cur += C+1            
        else:
            cur += 1
        if count >= K:
            break
    if count < K:
        return set(range(N))
    return cand

cand1 = F(S)
cand2 = F(S[::-1])
cand2 = set(N-1-x for x in cand2)
cand3 = F(S[1:])
cand3 = set(x+1 for x in cand3)
s = cand1 & cand2
s = s & cand3
s = sorted(list(s))
s = [x+1 for x in s]
print(*s, sep='\n')

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
sep = "x"*c
s = input().split(sep) if sep != "" else [input()]

result = []

def check_must(ary):
    holiday = c
    result2 = {}
    result3 = []
    for i in range(len(ary)):
        if ary[len(ary)-i-1] == "o" and holiday >= c:
            result2[len(ary)-i-1] = True
            holiday = 0
        else:
            holiday += 1
    holiday = c
    for i in range(len(ary)):
        if ary[i] == "o" and holiday >= c:
            if i in result2:
                result3.append(i)
            holiday = 0
        else:
            holiday+=1

    return result3

number = 0
for i in range(len(s)):
    number+= i * c
    result4 = check_must(s[i])
    for j in range(len(result4)):
        result.append(number + result4[j] + 1)
    number+= len(s[i])

if len(result) <= c:
    for i in range(len(result)):
        print(result[i])

Submission status: Wrong Answer

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

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

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

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

for i in sorted(list(answer1 & answer2)):
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 22:17:26 2020

@author: liang
"""
from itertools import combinations as comb

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

ans_list = []
common_list = []
Sift = [i+1 for i in range(len(S)) if S[i] == 'o'] 
#print(Sift)
check_list = list(comb(Sift,K))

for check in check_list:
    #for i in range(len(check)-1):
    if all(check[i+1] - check[i] >= C for i in range(len(check)-1)):
            ans_list.append(check)

#print(ans_list)
ans_set = set(ans_list)
for key in ans_list[0]:
    if all(key in ans for ans in ans_set) :
        common_list.append(key)
for _ in common_list:
    print(_)

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
owari = dp[i] - k
while i < N:
    if dp[i] < k:
        # print(i, cnt, ans, k, ans + C + 1)
        if cnt == 1:
            print(ans + 1)
        i = max(ans + C + 1, i)
        ans = 0
        cnt = 0
        k -= 1
        if k == owari:
            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 = input()
L = [0]*(N)
ans = 0
P = []
for i in range(N):
    if S[i] == "x":
        ans += 1
    L[i] = ans
for i in range(C):
    L.append(ans)
Q = []
for i in range(N):
    flag = 0
    if S[i] == "o":
        #もし1日目で働ける場合
        if L[i+C]-L[i] <= C:
            #累積の休み日数がC以下
            P.append(i+1)
        else:
            if len(P) >= 1:
                s = P.copy()
                Q.append(s)
                P.clear()
    else:
        if len(P) >= 1:
            s = P.copy()
            Q.append(s)
            P.clear()
Q.append(P)
if len(Q) == K:
    for i in range(len(Q)):
        if len(Q[i]) == 1:
            print(*Q[i])

Submission status: Wrong Answer

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


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

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

    forward = []
    day = 0
    cnt = 0
    for q in Q:
        if day < q:
            forward.append(q)
            day = q + C
            cnt += 1
        if cnt == K:
            break
    
    res = []
    day = INF
    cnt = 0
    for q in reversed(Q):
        if q + C < day:
            day = q
            cnt += 1
            bisect.insort(forward, q)
        if cnt == K:
            break
    
    for i in range(len(forward) - 1):
        if forward[i] == forward[i+1]:
            print(forward[i])
        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K, C = map(int, input().split())
S = [c == "o" for c in input().strip()]

prev = -C - 1
count = 0
work_l = []
for i, c in enumerate(S):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_l.append(i)

prev = -C - 1
count = 0
work_r = []
for i, c in enumerate(reversed(S)):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_r.append(N - 1 - i)

work_r.reverse()

for l, r in zip(work_l, work_r):
	if l == r:
		print(l + 1)

Submission status: Wrong Answer

Solution code:
import sys
n,k,c=map(int,input().split())
s=input()
work=[]
for i in range(n):
    if s[i]=="o": work.append(i)

l=len(work)
if l==1: print(1);sys.exit()
if l==2:
    if k==2: print(1);sys.exit()
    if k==1: print(0);sys.exit() 
if n==c:
    if len(work)==1: print(1)
    else: print(0)
    sys.exit()

dp1=[0 for i in range(n)]

if s[0]=="o": dp1[0]=1

for i in range(1,c+1):
    if s[i]=="o": dp1[i]=1
    else: dp1[i]=dp1[i-1]
for i in range(c+1,n):
    if s[i]=="o": dp1[i]=dp1[i-c-1]+1
    else: dp1[i]=dp1[i-1]


dp2=[0 for i in range(n)]
if s[n-1]=="o": dp2[n-1]=1
for i in range(n-2,n-c-2,-1):
    if s[i]=="o": dp2[i]=1
    else: dp2[i]=dp2[i+1]
for i in range(n-c-2,-1,-1):
    if s[i]=="o": dp2[i]=dp2[i+c+1]+1
    else: dp2[i]=dp2[i+1]


ans=[]
if dp2[work[0]+1]<k: ans.append(work[0])

for i in range(1,l-1):
    p=work[i-1]
    tmp=dp1[p]
    if p+c+1<=work[i]: tmp+=dp2[work[i]+1] 
    elif p+c+1<n: tmp+=dp2[p+c+1]
    if tmp<k: ans.append(work[i])

if dp1[work[l-1]-1]<k: ans.append(work[l-1])

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
n,k,c = map(int,input().split())
dp = [0]*(n+c+2)
s = input()
idx = []
for i in range(n):
    if s[i]=='o':
        idx.append(i+1)
for i in idx:
    dp[i] += 1
    dp[i+c+1] -= 1
dp = np.cumsum(dp).tolist()

for i in idx:
    tmp = copy.deepcopy(dp)
    for j in range(i, i+c+1):
        tmp[j] -= 1

    cnt = 0
    flg = False
    for j in range(len(tmp[1:-1])):
        if tmp[1+j]!=0 and flg==False:
            flg = True
            cnt += 1
        if tmp[1+j]!=0 and flg:
            continue
        if tmp[1+j]==0:
            flg = False
    if cnt<k:
        print(i)

Submission status: Wrong Answer

Solution code:
N,K,C = list(map(int,input().split()))
S = input()
forward = [0 for i in range(N)]
backward = [0 for i in range(N)]

m = 0
for i in range(N):
  if S[i] == "o":
    m += 1
    if i-C < 0 :
      m = 1
    else:
      m = min(m,forward[i-C]+1)
  forward[i] = m

    
ruiseki = []
cnt = 0
for char in S:
  if "x" == char :
    cnt+=1
    ruiseki.append(cnt)

for i in range(N-1, -1, -1):
  if i<N-1:
    backward[i] = backward[i+1] 
  if S[i] == "o" :
    if i+C >= N:
      backward[i] = 1
    else:
      backward[i] = backward[i+C]+1
f = [0]+forward[:-1]
b = backward[1:]+[0]   
for idx,ch in enumerate(S):
  if ch == "o":
    if f[idx]+b[idx]< K:
      print(idx+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

must_day = set(list(range(1,n+1)))

def dfs(day, rest, workdays):
  if rest < 1:
    global must_day, kouho_n
    kouho_n += 1
    must_day = must_day & set(workdays)
    return
  elif day > n:
    return
  else:
    if day - workdays[-1] > c and s[day-1] == 'o':
      dfs(day+1, rest-1, workdays+[day])
    dfs(day+1, rest, workdays)
    return
dfs(1, k, [-c])

if kouho_n > 1:
  for d in must_day:
    print(d)

Submission status: Wrong Answer

Solution code:
from bisect import *

N, K, C = map(int, input().split())
S = input()
T = [i for i, x in enumerate(S, 1) if x == 'o']
lst = []
l = []
last = T[0]
for t in T:
    if t <= last+C:
        l.append(t)
    else:
        lst.append(l)
        l = [t]
        last = t
lst.append(l)
if len(lst) <= K:
    for i in range(K-1, 0, -1):
        if len(lst[i]) == 1:
            lst[i-1] = lst[i-1][:bisect_left(lst[i-1], lst[i][0]-C)]
    for l in lst:
        if len(l) == 1:
            print(l[0])
else:
    print()

Submission status: Wrong Answer

Solution code:



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



set1 = set()
count = 0
p = 0

while p < n and count < k:
    if s[p] == 'x':
        p += 1
        continue

    set1.add(p)
    p += c + 1
    count += 1


set2 = set()
count = 0
p = n - 1

while p >= 0 and count < k:
    if s[p] == 'x':
        p -= 1
        continue

    set2.add(p)
    p -= (c + 1)
    count += 1    

# print (set1)
# print (set2)
res = set1 & set2

for i in sorted(list(res)):
    print (i + 1)

Submission status: Wrong Answer

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

l = [0 for _ in range(n + 1)]
prev = -c
for i in range(1, n + 1):
    l[i] = l[i - 1]
    if prev + c < i and s[i - 1] == 'o':
        l[i] += 1
        prev = i
r = [0 for _ in range(n + 1)]
prev = n + c
for i in range(n - 1, -1, -1):
    r[i] = r[i + 1]
    if i < prev - c and s[i] == 'o':
        r[i] += 1
        prev = i
cnt = [1 if c == 'o' else 0 for c in s]
for i in range(n):
    if 0 < i - c:
        cnt[i] += l[i - c]
    if i + c + 1 < n + 1:
        cnt[i] += r[i + c + 1]
ans = [s[i] == 'o' and cnt[i] == k for i in range(n)]
prev = -c
for i in range(n):
    if s[i] == 'o' and cnt[i] == k:
        if i <= prev + c:
            ans[i] = False
        prev = i
prev = n + k
for i in range(n - 1, -1, -1):
    if s[i] == 'o' and cnt[i] == k:
        if prev - c <= i:
            ans[i] = False
        prev = i
for i in range(n):
    if ans[i]:
        print(i + 1)

Submission status: Wrong Answer

Solution code:
print()

Submission status: Wrong Answer

Solution code:
import itertools
n, k, c = map(int, input().split())
s = input()
a = [i for i in range(n)]
b = list(itertools.combinations(a,k))
for i in b:
    for j in range(k):
        if s[i[j]] == 'x':
            break
        if j != 0:
            if i[j] - i[j-1] <= c:
                break
        a = set(a) & set(i)

for i in a:
    print(i+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 22:17:26 2020

@author: liang
"""
from itertools import combinations as comb

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

ans_list = []
common_list = []
Sift = [i+1 for i in range(len(S)) if S[i] == 'o'] 
#print(Sift)
check_list = list(comb(Sift,K))

for check in check_list:
    #for i in range(len(check)-1):
    if all(check[i+1] - check[i] >= C for i in range(len(check)-1)):
            ans_list.append(check)

#print(ans_list)
for key in ans_list[0]:
    if all(key in ans for ans in ans_list) :
        common_list.append(key)
for _ in common_list:
    print(_)

Submission status: Wrong Answer

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

S = [s=="o" for s in S]
dpL = [(0,-1)]*N
dpR = [0]*N
if S[0]:
    dpL[0] = (1,0)
for i,s in enumerate(S[1:],1):
    dpL[i] = dpL[i-1]
    if not s:
        continue
    if i-C-1>=0:
        if dpL[i-C-1][0]+1>dpL[i][0]:
            dpL[i] = (dpL[i-C-1][0]+1,i)

dpR[-1] = int(S[-1])
for i,s in enumerate(S[-2::-1],1):
    i = N-i-1
    dpR[i] = dpR[i+1]
    if not s:
        continue
    if i+C+1<N:
        dpR[i] = max(dpR[i],dpR[i+C+1]+1)

for i,s in enumerate(S):
    if not s: continue
    ans = 0
    j = i+1
    if i>0:
        ans += dpL[i-1][0]
        j = max(dpL[i-1][1]+C+1,i+1)
    if j<N:
        ans += dpR[j]
    
    if ans == K-1:
        print(i+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E - Yutori
# モジュールのインポート
import itertools

# 標準入力の取得
N,K,C = list(map(int, input().split()))
S = input()

# 求解処理
# "o"の日だけリスト化
shift_list = []
for n in range(N):
    if S[n] == "o":
        shift_list.append(n+1)

# 条件を満たすような組合せを全探索
result = set(shift_list)
for shift in itertools.combinations(shift_list, K):
    can_work = True
    for k in range(K-1):
        if shift[k+1] - shift[k] <= C:
            can_work = False
            break

    if can_work:
        result &= set(shift)

for r in result:
    print(r)

Submission status: Wrong Answer

Solution code:
print('')

Submission status: Wrong Answer

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

cnt = 0
day = []

while cnt < n:
    if s[cnt] == 'o':
        day.append(cnt)
        cnt += c + 1
    else:
        cnt += 1

if len(day) > k:
    exit()

day2 = [[] for _ in range(len(day))]
for i in range(len(day)-1):
    for j in range(day[i], day[i+1]):
        if s[j] == 'o':
            day2[i].append(j)
for j in range(day[-1], n):
    if s[j] == 'o':
        day2[-1].append(j)

cnt2 = -1
ans = []

for i in range(len(day2)):
    if len(day2[i]) == 1:
        cnt2 = i
        tmp = day2[i][0]
        tmp2 = day2[i][0]
        ans.append(tmp)
        break

if cnt2 != -1:
    if cnt2 != 0:
        for i in day2[cnt2-1::-1]:
            for j in range(len(i)):
                if tmp - i[-j-1] >= c + 1:
                    tmp = i[-j-1]
                    if j == len(i) - 1:
                        ans.append(tmp)
                    break
    if cnt2 != len(day2) - 1:
        for i in day2[cnt2+1:]:
            for j in range(len(i)):
                if i[j] - tmp2 >= c + 1:
                    tmp2 = i[j]
                    if j == len(i) - 1:
                        ans.append(tmp2)
                    break
"""
else:
    max1 = 10**10
    for i in range(len(day2)):
        if len(day2[i]) < max1:
            cnt3 = i
            max1 = len(day2[i])
    li = []
    for ii in range(len(day2[cnt3])):
        tmp = day2[cnt3][ii]
        if cnt3 != 0:
            for i in day2[cnt3-1::-1]:
                for j in range(len(i)):
                    if tmp - i[-j-1] >= c + 1:
                        tmp = i[-j-1]
                        if j == len(i) - 1:
                            li.append(tmp)
                        break

        tmp2 = day2[cnt3][ii]
        if cnt3 != len(day2) - 1:
            for i in day2[cnt3+1:]:
                for j in range(len(i)):
                    if i[j] - tmp2 >= c + 1:
                        tmp2 = i[j]
                        if j == len(i) - 1:
                            li.append(tmp2)
                        break
    li.sort()
    tmp3 = -1
    cnt = 0
    for i in range(len(li)):
        if tmp3 != li[i]:
            if cnt == len(day2[cnt3]):
                ans.append(tmp3)
            tmp3 = li[i]
            cnt = 0
        else:
            cnt += 1
    if cnt == len(day2[cnt3]):
        ans.append(tmp3)

ans.sort()
for i in ans:
    print(i+1)
"""

Submission status: Wrong Answer

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


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

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, C, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if c == 0:
    ls = [i for i in range(n) if s[i]=='o']
    if len(ls) == k:
        for i in ls:
            print(i+1)
    else:
        print()
    exit(0)

dp = [[0]*2 for i in range(n+1)]  # dp[i][0/1] i日目が(x/o)のときの最大値

for i in range(n-1,-1,-1):
    dp[i][0] = max(dp[i+1][0], dp[i+1][1])
    if s[i] == 'o':
        if i+c+1 >= n:
            dp[i][1] = 1
        else:
            dp[i][1] = max(dp[i+c+1][0], dp[i+c+1][1]) + 1

if max(dp[0][0],dp[0][1]) == k:
    ls = [[] for i in range(k+2)]
    for i in range(n):
        x = dp[i][1]
        if x >= 1:
            if len(ls[x+1]) == 1 and i+1 <= ls[x+1][0]+c:
                continue
            ls[dp[i][1]].append(i+1)
    ans = []
    for l in ls:
        if len(l) == 1:
            ans.append(l[0])
    ans.sort()
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 前からと後ろからでcandに入れて両方に入るところ
N, K, C = lr()
S = sr()
cand1 = set()
cand2 = set()

def F(S):
    cand = set()
    count = 0
    cur = 0
    while cur < len(S):
        if S[cur] == 'o':
            count += 1
            cand.add(cur)
            cur += C+1            
        else:
            cur += 1
        if count >= K:
            break
    return cand

cand1 = F(S)
cand2 = F(S[::-1])
cand2 = set(N-1-x for x in cand2)
s = cand1 & cand2
s = sorted(list(s))
s = [x+1 for x in s]
print(*s, sep='\n')

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    """Segment Tree (Point Update & Range Query)
    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)
    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N - 1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )

    def __getitem__(self, k):
        return self.segtree[self.N - 1 + k]

    def query(self, low, high):
        # query [l, r)
        low, high = low + self.N, high + self.N
        left_ret, right_ret = self.default, self.default
        while low < high:
            if low & 1:
                left_ret = self.f(left_ret, self.segtree[low - 1])
                low += 1
            if high & 1:
                high -= 1
                right_ret = self.f(self.segtree[high - 1], right_ret)
            low, high = low >> 1, high >> 1
        return self.f(left_ret, right_ret)


def main() -> None:
    N, K, C = map(int, input().split())
    S = [1 if s == "o" else 0 for s in input()]
    left, right = [-1] * N, [-1] * N
    max_v = -1
    for i in range(N):
        if i - C - 1 >= 0:
            max_v = max(max_v, left[i - C - 1])
        if S[i] == 1:
            left[i] = max_v + 1
    max_v = -1
    for i in reversed(range(N)):
        if i + C + 1 <= N - 1:
            max_v = max(max_v, right[i + C + 1])
        if S[i] == 1:
            right[i] = max_v + 1
    work_day = [max(0, left[i] + right[i] + 1) for i in range(N)]
    #print(work_day)
    if max(work_day) > K:
        return
    segt = SegmentTree.create_from_array(work_day, max, 0)
    ans = []
    for i in range(N):
        m = max(segt.query(max(0, i - C), i), segt.query(i+1, min(i + 1 + C, N)))
        if m >= K:
            continue
        # m = max(segt.query(0, max(0, i - C)), segt.query(min(N, i + 1 + C), N))
        # if m >= K + 1:
        #     continue
        ans.append(i + 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# 必ず働く日：その日に働かなければK日働くを達成できない
# その日を×にしたら最大限に詰めても条件を満たさない
# 最大働ける日数は貪欲法で行ける?
# 計算オーダー不足
# メモ化

count = 0
i = 0
work_day = []
memo_maxmum_worked_day = [0] * n
while i < n:
    if s[i] == 'o':
        work_day.append(i)
        count += 1
        for j in range(i, i + c):
            if j < n:
                memo_maxmum_worked_day[j] = count
        i += c + 1
    else:
        memo_maxmum_worked_day[i] = count
        i += 1
#print(count)
#print(work_day)

if count > k:
    pass
else:
    need_day = []
    while work_day:
        flag = True
        check_day = work_day.pop()
        tmp_work_day = []
        count = 0
        i = check_day
        count = memo_maxmum_worked_day[check_day] - 1
        while i < n:
            if memo_maxmum_worked_day[i] == count:
                flag = False
                break
            if s[i] == 'o' and i != check_day:
                tmp_work_day.append(i)
                count += 1
                i += c + 1
            else:
                i += 1

        if count < k and flag == True:
            need_day.append(check_day)

    need_day.sort()
    for i in need_day:
        print(i+1)

Submission status: Wrong Answer

Solution code:
a=0

Submission status: Wrong Answer

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

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

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

for i in sorted(list(answer1 & answer2)):
    print(i)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

n,k,c = map(int, input().split())
S = [True if i=='o' else False for i in input()]

if n == c:
    ANS = []
    if S[0] and not(S[-1]):
        ANS.append(1)
    elif not(S[0]) and not(S[-1]):
        ANS.append(n)
    print(*ANS,sep='\n')
    exit()



left = [0]*n
right = [0]*n
c = c+1
if S[0]:
    left[0] = 1

for i in range(1, c):
    if S[i]:
        left[i] = 1
    left[i] = max(left[i], left[i-1])

for i in range(c, n):
    if S[i]:
        left[i] = left[i-c] + 1
    else:
        left[i] = left[i-1]
if S[-1]:
    right[-1] = 1
for i in range(n-c, n-1)[::-1]:
    if S[i]:
        right[i] = 1
    right[i] = max(right[i], right[i+1])
for i in range(n-c)[::-1]:
    if S[i]:
        right[i] = right[i+c] + 1
    else:
        right[i] = right[i+1]

ans = []
for i in range(n):
    if S[i]:
        tl = 0
        tr = 0
        if i>0:
            tl = left[i-1]
        if i<n-1:
            tr = right[i+1]
        if tl + tr < k:
            ans.append(i+1)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

must_day = set(list(range(1,n+1)))

def dfs(day, rest, workdays):
  if rest < 1:
    global must_day
    must_day = must_day & set(workdays)
    return
  elif day > n:
    return
  else:
    if day - workdays[-1] > c and s[day-1] == 'o':
      dfs(day+1, rest-1, workdays+[day])
    dfs(day+1, rest, workdays)
    return
dfs(1, k, [-c])
for d in must_day:
  print(d)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,k,c=map(int,input().split())
s=input().rstrip()
nc=[0]*n
co=0
d=c+1
for i in range(n):
    if s[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[i]+=1
        else:
            d+=1
    if co==k:
        break
sn=list(s)
sn.reverse()
co=0
d=c+1
for i in range(n):
    if sn[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[n-1-i]+=1
        else:
            d+=1
    if co==k:
        break
for i in range(n):
    if nc[i]==2:
        print(i+1)

Submission status: Wrong Answer

Solution code:
N,K,C = map(int, input().split(' '))
S = input()
ans = []
for i in range(len(S)):
  p = 0
  su = 0
  while p < N:
    if p == i:
      p = p + 1
      continue
    if S[p] == "o":
      p = p + C
      su  = su + 1
      if su == K:
        break
    else:
      p = p + 1
  if su != K:
    ans.append(i+1)
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
import re
import itertools
import numpy as np

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:
    try:
        min_diff = min(np.diff(i, n=1))
    except ValueError:
        min_diff = c
    if min_diff >= c + 1:
        if first:
            ans = set(list(i))
            first = False
        else:
            tmp = set(list(i)) & ans
            ans = set()
            ans = tmp

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