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

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

Submission status: Wrong Answer

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

# 前貪欲
ansl = []
before = -float("inf")
for idx,s in enumerate(sl):
    if s == "o" and before + c < idx:
        before = idx
        ansl.append(idx)

# 後貪欲
ansl2 = []
before = -float("inf")
for idx,s in enumerate(sl[::-1]):
    if s == "o" and before + c < idx:
        before = idx
        ansl2.append(n-idx-1)



for a1,a2 in zip(ansl[:k], ansl2[::-1][:k]):
    if a1 == a2:
        print(a1+1)

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = 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+1)
            holiday = 0
        else:
            holiday+=1

    return result3

result = check_must(s)

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

# 前貪欲
ansl = []
before = -float("inf")
for idx,s in enumerate(sl):
    if s == "o" and before + c < idx:
        before = idx
        ansl.append(idx)

# 後貪欲
ansl2 = []
before = -float("inf")
for idx,s in enumerate(sl[::-1]):
    if s == "o" and before + c < idx:
        before = idx
        ansl2.append(n-idx-1)

for a1,a2 in zip(ansl[:k], ansl2[::-1][:k]):
    if a1 == a2:
        print(a1)

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 abs(shift[k+1] - shift[k]) <= C:
            can_work = False
            break

    if can_work:
        result &= set(shift)

    if len(result) == 0:
        break

# 結果出力
for r in result:
    print(r)

Submission status: Wrong Answer

Solution code:
N, K, C = map(int, input().split())
S = input()
 
work_days_list = []
whole_days_list = []
for i in range(N):
    new_work_days_list = []
    if S[i] == 'o' and N - i >= K:
        new_work_days_list.append([i])
    if S[i] == 'x':
        continue
    for work_days in work_days_list:
        if N - i >= K - len(work_days):
            new_work_days_list.append(work_days)
        if i - work_days[-1] > C:
            new_work_days = work_days + [i]
            if len(new_work_days) == K:
                whole_days_list.append(set(new_work_days))
            else:
                new_work_days_list.append(new_work_days)
    work_days_list = new_work_days_list

if len(whole_days_list) == 0:
    exit()

tmp_days = whole_days_list.pop()
while len(whole_days_list) > 0:
    tmp_days &= whole_days_list.pop()

for day in tmp_days:
    print(day+1)

Submission status: Wrong Answer

Solution code:
def main():
    n,k,c=map(int,input().split())
    S=input()
    l1=[[0,0] for _ in range(n)]
    l2=[0]*n
    memo=[0]*n
    x=0
    for i in range(n):
        if S[i]=="o" and memo[i]==0:
            x+=1
            l1[i][0]=x
            l1[i][1]=i+c+1
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        elif S[i]=="o" and memo[i]==1:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
        elif S[i]=="x" and memo[i]==0:
            l1[i][0]=x
            l1[i][1]=i+1
        else:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
    S_=S[::-1]
    memo=[0]*n
    x=0
    for i in range(n):
        if S_[i]=="o" and memo[i]==0:
            x+=1
            l2[i]=x
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        else:
            l2[i]=x
    l2=l2[::-1]
    ans=0
    for i in range(n):
        if S[i]=="o":
            x=0
            if i!=0:
                x+=l1[i-1][0]
            if i==0:
                x+=l2[0]
            else:
                if l1[i-1][1]<n and i<n-1:
                    x+=l2[max(l1[i-1][1],i+1)]
            if x<k:
                print(i+1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = [1 if i == "o" else 0 for i in list(input())]
left = [-1] * n
right = [-1] * n
cool = 0
now=0
for i in range(n):
    if s[i] == 0:
        cool-=1
        continue
    if now >= k:
        left[i] = now
    elif cool > 0:
        left[i] = now
        cool -= 1
    else:
        now += 1
        cool=c
        left[i] = now
cool = 0
now=k+1 if k!=0 else k
for i in range(n-1,-1,-1):
    if s[i] == 0:
        cool-=1
        continue
    if now <= 0:
        right[i] = now
    elif cool > 0:
        right[i] = now
        cool -= 1
    else:
        now -= 1
        cool=c
        right[i] = now
ans = set([])
redlist=set([])
for i in range(n):
    if left[i] not in redlist and left[i] != -1 and left[i] <= right[i]:
        if left[i] in ans:
            ans.remove(left[i])
            redlist.add(left[i])
        else:
            ans.add(left[i])
for i in ans:
    print(left.index(i)+1)

Submission status: Wrong Answer

Solution code:
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
dpp = [0]*(n+c+2)
dpp[0] = dp[0]
for i in range(1, len(dp)):
    dpp[i] = dpp[i-1]+dp[i]
for i in idx:
    tmp = copy.deepcopy(dpp)
    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:
# -*- coding: utf-8 -*-
import sys

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


for k in range(10):
    nassign_t = [False]*N
    num = 0
    i = k
    while i<N and num<K:
        if S[i]=='o':
            nassign_t[i] = True
            num += 1
            i += C+1
        else:
            i += 1
    if num==K:
        if k==0:
            for j in range(N):
                assign_t[j] |= nassign_t[j]
        else:
            for j in range(N):
                assign_t[j] &= nassign_t[j]
            
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:
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
for i in range(1,len(dp)):
    dp[i] = dp[i]+dp[i-1]       
dpp = [0]*(n+c+2)
dpp[0] = dp[0]
for i in range(1, len(dp)):
    dpp[i] = dpp[i-1]+dp[i]
for i in idx:
    tmp = copy.deepcopy(dpp)
    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 = map(int,(input().split()))
S = list(input())
ol = []
ans = []
for i in range(N):
    if S[i] == "o":
        ol.append(i)

for i in ol:
    now = ol[0]
    c = 1
    for j in ol:
        if j > now+C:
            if j != i:
                now = j
                c += 1
        if c >= K:
            break
    if c < K:
        ans.append(i) 
for i in ans:
    print(i+1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def check_must(arr, pos, k ,c):
    res = arr.copy()
    del res[pos]
    for t in combinations(res, k):
        flg = False
        for t1, t2 in zip(t[:-1], t[1:]):
            if t2 - t1 <= c:
                flg = True
                break
        if flg:
            continue
        else:
            return False, arr
    return True, arr

def main():
    n, k, c = [int(i) for i in input().split()]
    s = [1 if i is 'o' else 0 for i in input()]
    res = [i+1 for i, b in enumerate(s) if b]
    cand = []
    pos = 0
    while pos < len(res):
        flg, res = check_must(res, pos, k, c)
        if flg:
            cand.append(res[pos])
            c -= 1
        pos+=1
    for c in cand:
        print(c)
    
if __name__ == '__main__':
    main()

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:
        ans = set(list(i))
        first = False
        break
    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)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def check_must(arr, pos, k ,c):
    res = arr.copy()
    del res[pos]
    for t in combinations(res, k):
        flg = False
        for t1, t2 in zip(t[:-1], t[1:]):
            if t2 - t1 <= c:
                flg = True
                break
        if flg:
            continue
        else:
            return False, arr
    return True, arr

def main():
    n, k, c = [int(i) for i in input().split()]
    s = [1 if i is 'o' else 0 for i in input()]
    res = [i+1 for i, b in enumerate(s) if b]
    cand = []
    pos = 0
    while pos < len(res):
        flg, res = check_must(res, pos, k, c)
        if flg:
            cand.append(res[pos])
            c -= 1
        pos+=1
    print(cand)
    
if __name__ == '__main__':
    main()

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 = ans + C + 1
        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 and k == 0:
    print(ans + 1)

Submission status: Wrong Answer

Solution code:

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

def main():
    import bisect
    from copy import deepcopy
    mod=10**9+7
    N,K,C=MI()
    S=input()
    pos=[]
    for i in range(N):
        if S[i]=="o":
            pos.append(i)
            

            
    #後ろから見ていく，i番目のoを選んだときに，どういうルートがとれるか，最長のものをLに格納，そのパスの長さをlengthに
    M=len(pos)
    L=[[] for _ in range(M)]
    length=[0]*(M+1)
    length[-1]=0
    maxl=0
    for i in range(M-1,-1,-1):
        a=pos[i]
        b=a+C
        se=bisect.bisect_right(pos,b)#C個より先を探す
        for j in range(se,M):
            if length[j]>=maxl-1:
                L2=deepcopy(L[j])
                for k in range(len(L2)):
                    L2[k].append(pos[i])
                
                L[i]+=L2
            else:
                break
        if L[i]==[]:
            L[i].append([pos[i]])
        length[i]=len(L[i][0])
        maxl=length[i]

    
    ans=set(pos)
    for i in range(M):
        if length[i]>=K:
            for j in range(len(L[i])):
                if len(L[i][j])>=K:
                    ans=ans & set(L[i][j])
                    
        else:
            break
                
    
    ans=list(ans)
    ans.sort()          
    for i in range(len(ans)):
        print(ans[i]+1)
            
    
        
    

main()

Submission status: Wrong Answer

Solution code:
def  check(index, k,table):
    if k < 0:
        return
    if index == n:
        if k == 0:
            for i, t in enumerate(table):
                if not t:
                    cand[i] = 0
        return
    for i, flag in enumerate(cand[index:],index):
        if flag:
            ta = table[:]
            ta[i] = 0
            check(i+1,k,ta)
            for j in range(k):
                if i+j+1<n:
                    table[i+j+1] = 0
            check(i+k+1,k-1,table)
import sys
sys.setrecursionlimit(10**6)        
n, K, c = map(int, input().split())
S = input()
cand = [0]*n
for i, s in enumerate(S):
    if s == 'o':
        cand[i] = 1
table = cand[:]
check(0, K,table)
print(*[i+1 for i, l in enumerate(cand) if l == 1], sep = '\n')

Submission status: Wrong Answer

Solution code:
import copy

n,k,c = map(int, input().split())
s = input()
S = []
lst = [[] for i in range(n)]
# print(lst)
for i in range(len(s)):
    if s[i]=="o":
        S.append(i)
# print("S:",S)
for i in range(len(S)-1):
    koho = S[i+1:]
    for j in koho:
        if j>S[i]+c:
            lst[S[i]].append(j)
    # lst[S[i]].append(S[i+1:])
# print("lst:",lst)



ans = []
for i in S:
    testlst = copy.deepcopy(lst)
    testlst[i] = []
    for j in range(n):
        if testlst[j]!=[]:
            if  testlst[j][0]==i:
                testlst[j].remove(i)
    # print("i,testlst:",i,testlst)

    count = 1
    if i==S[0]:
        if len(S)>1:
            num = S[1]
        else:
            num = S[-1]
    else:
        num = S[0]
    while testlst[num]!=[]:
        num = testlst[num][0]
        count += 1
    if count < k:
        ans.append(i+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


for i in range(10):
    nassign_t = [False]*N
    num = 0
    while i<N and num<K:
        if S[i]=='o':
            nassign_t[i] = True
            num += 1
            i += C+1
        else:
            i += 1
    if num==K:
        if i==0:
            for j in range(N):
                assign_t[j] |= nassign_t[j]
        else:
            for j in range(N):
                assign_t[j] &= nassign_t[j]
            
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:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,k,c=map(int, readline().rstrip().split())
    ss=readline().rstrip()

    for i in range(n):
        cnt=0
        if ss[i]=="x":
            continue
        if i>0:
            j=0
            while j<i:
                if ss[j]=="o" and (j+c)<i:
                    cnt+=1
                    j+=c
                j+=1

        if i<(n-1):
            j=(i+c+1)
            while j<n:
                if ss[j]=="o":
                    cnt+=1
                    j+=c
                j+=1
        if cnt==k-1:
            print(i+1)

    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
N,K,C = map(int,(input().split()))
S = list(input())
ol = []
ans = []
for i in range(N):
    if S[i] == "o":
        ol.append(i)

for i in ol:
    now = ol[0]
    c = 1
    for j in ol:
        if j > now+C:
            if j != i:
                now = j
                c += 1
        if c >= K:
            break
    if c < K:
        ans.append(i) 
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
# from heapq import heapify, heappop, heappush
# from bisect import bisect_left, bisect_right
# from collections import defaultdict
# import sys
# input = lambda: sys.stdin.readline().rstrip()
# sys.setrecursionlimit(10**9)
# MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
N, K, C = inpl()
S = input()
Ws = []
next_w = [0]*N
prev = None
for i in range(N):
    if S[i] == 'o':
        Ws.append(i)
        if prev is not None:
            next_w[prev] = i
            prev = i
s = 0
m = -2
n = -1
best_until = [None] * N
for i in range(N):
    if i == m+1:
        s += 1
    if S[i] == 'o':
        n += 1
        if i > m:
            best_until[n] = (s,1,n)
        elif n > 0:
            m = i + C
            best_until[n] = (s,0,best_until[n-1][2])
        else:
            m = i + C
            best_until[n] = (s,0,None)

w = 0
m = N
best_from = [None]*N
for i in range(N-1,-1,-1):
    if i < m and S[i] == 'o':
        w += 1
        m = i - C
    best_from[i] = w

for i, w in enumerate(Ws):
    s, c, b = best_until[i]
    if c == 1:
        if i == 0:
            s, c, b = 0, 0, 0
            wb = -1
        else:
            s, c, b = best_until[i-1]
            if b == None:
                wb = None
            else:
                wb = Ws[b]
    else:
        if b is None:
            wb = -1
        else:
            wb = Ws[b]

    if wb < N - 1:
        wf = best_from[wb+1]
    else:
        wf = 0
    print(wf, s)
    if wf + s < K:
        print(w+1)

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,i+1)
    if j<N:
        ans += dpR[j]
    
    if ans < K:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import itertools
n, k, c = map(int, input().split())
s = input()
counto = s.count("o")
count = 0
a = []
b = [0]
for i in range(n):
    if s[i] == "o":
        a.append(i)
for i in list(itertools.combinations(a, k)):
    for j in range(len(i)-1):
        if i[j] - i[j-1]<=c:
            break
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
n, k, c = [int(x) for x in input().split()]
s = input()
counts = [[0] * 2 for i in range(n)]
for i in range(n):
    if s[i] == 'x':
        if i > 0:
            counts[i] = [max(counts[i - 1]), 0]
        else:
            counts[0]= [1, 0]
        continue
    if i == 0:
        counts[0]= [1, 1]
    elif i <= c:
        counts[i] = [max(counts[i - 1]), 1]
    else:
        counts[i] = [max(counts[i - 1]), max(counts[i - c - 1]) + 1]
r = []
checkk = k
for i in range(n - 1, -1, -1):
    if counts[i][1] == checkk:
        if counts[i][0] != checkk:
            r.append(i + 1)
        checkk = counts[i][1] - 1
for i in range(len(r) - 1, -1, -1):
    print(r[i])

Submission status: Wrong Answer

Solution code:
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
for i in range(1,len(dp)):
    dp[i] = dp[i]+dp[i-1]       

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 = 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)
else:
    print()

Submission status: Wrong Answer

Solution code:
#e

import itertools

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

S2 = [i+1 for i,s in enumerate(S) if s=="o"]

def is_ok(sb):
  return sum([1 if sb[i+1]-sb[i]<=C else 0 for i in range(len(sb)-1)])

log = {i:0 for i in S2}

count = 0

cs = []
for c in itertools.combinations(S2, K):
  if is_ok(c)==0:
    count += 1
    for ci in c:
      log[ci] += 1

for i,c in log.items():
  if c==count:
    print(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
    k = 0
    for q in Q:
        if day < q:
            forward.append(q)
            day = q + C
            k += 1
    
    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:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
N,K,C = LI()
S = input()
dp = [0 for _ in range(N)]
j = 0
last = -INF
for i in range(N):
    if S[i] == 'o':
        if i - last > C:
            j += 1
            last = i
        dp[i] = j

if j != K:
    exit(0)

last = INF
j = K + 1
for i in range(N-1,-1,-1):
    if S[i] == 'o':
        if last - i > C:
            j -= 1
            last = i
        if dp[i] > 0:
            dp[i] = j

last = -1
cnt = 0
for i in range(N):
    if dp[i] > 0:
        if dp[i] != last:
            if cnt == 1:
                print (last_i + 1)
            cnt = 0
            last = dp[i]
            last_i = i
        cnt += 1
if cnt == 1: print (last_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


for i in range(10):
    nassign_t = [False]*N
    i = 0
    num = 0
    while i<N and num<K:
        if S[i]=='o':
            nassign_t[i] = True
            num += 1
            i += C+1
        else:
            i += 1
    if num==K:
        if i==0:
            for j in range(N):
                assign_t[j] |= nassign_t[j]
        else:
            for j in range(N):
                assign_t[j] &= nassign_t[j]
            
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:
from collections import Counter,defaultdict
n,k,c = map(int,input().strip().split())
st = input()
i = n-1
j = 0
temp_ls = [0]*n
count = 0
while i>=0 and j<=c:
    if st[i]=='o':
        temp_ls[i] = 1
        count = 1
    else:
        temp_ls[i] = count
    i -= 1
    j += 1

#print(temp_ls)
while i>=0:
    #print(i)
    if st[i]=='o':
        j = i+c
        while j<n and st[j]=='x':
            j += 1
        if j==n:
            temp_ls[i] = 1
        else:
            temp_ls[i] = temp_ls[j] + 1
        count += 1
    else:
        temp_ls[i] = count
    i -= 1
#print(temp_ls)
#Somthing wrong
freq_dic = defaultdict(int)
for i,val in enumerate(temp_ls):
    if st[i]=='o':
        freq_dic[val] += 1
#print(freq_dic)
dic = dict(reversed(sorted(freq_dic.items(),key = lambda x: x[1])))
#print(dic)
si_value = -1
for key,val in dic.items():
    if val==1:
        si_value = key
#print(si_value)
ans = []
if si_value!=-1:
    i= 0
    for i in range(n):
        if st[i]=='o' and temp_ls[i]==si_value:
            break
    ans.append(i+1)
    #print(i,ans)
    i += c
    si_value -=  1
    while si_value>1:
        freq_count = freq_dic[si_value]
        #print(si_value,freq_count)
        f = 0
        while freq_count>0 and i<n:
            if st[i]=='o' and freq_count==1:
                f = 1
                break
            if st[i]=='o':
                freq_count -= 1
            i += 1
        if f:
            ans.append(i)
        si_value -= 1
    cn = 0
    li = -1
    for k in range(ans[-1]+c,n):
        if st[k]=='o':
            cn += 1
            li = k
    if cn==1:
        ans.append(li+1)
                   
    for val in ans:
        print(val)

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:
        print(i+1)

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = [1 if i == "o" else 0 for i in list(input())]
left = [-1] * n
right = [-1] * n
cool = 0
now=0
for i in range(n):
    if s[i] == 0:
        cool-=1
        continue
    if now >= k:
        left[i] = now
    elif cool > 0:
        left[i] = now
        cool -= 1
    else:
        now += 1
        cool=c
        left[i] = now
cool = 0
now=k+1 if c!=0 else k
for i in range(n-1,-1,-1):
    if s[i] == 0:
        cool-=1
        continue
    if now <= 0:
        right[i] = now
    elif cool > 0:
        right[i] = now
        cool -= 1
    else:
        now -= 1
        cool=c
        right[i] = now
ans = set([])
redlist=set([])
for i in range(n):
    if left[i] not in redlist and left[i] != -1 and left[i] == right[i]:
        if left[i] in ans:
            ans.remove(left[i])
            redlist.add(left[i])
        else:
            ans.add(left[i])
for i in ans:
    print(left.index(i)+1)