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:
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
            x = bisect.bisect_left(forward, q)
            if x != len(forward) and forward[x] == q:
                res.append(q)
        if cnt == K:
            break
    
    if len(res) == 0:
        print("")
    else:
        for r in reversed(res):
            print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def is_possible(w, K, C):
    #print(w)
    work = 1
    last = w[0]
    for i in range(1, len(w)):
        if w[i]>= last+C+1:
            last = w[i]
            work += 1
            #print("work",w[i])
        if work >= K:
            break
    if work >= K:
        return True
    else:
        return False
        

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

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

if len(working_days) == 1:
    print(working_days[0])
else:
    for i in range(len(working_days)):
        if i==0:
            before = []
        else:
            before = working_days[:i]
        if i==len(working_days)-1:
            after = []
        else:
            after = working_days[i+1:]
        w = before + after
        if not is_possible(w, K, C):
            print(working_days[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)
    appr = set(can_work)
    for v in comb:
        for i, j in enumerate(v[:-1]):
            if v[i + 1] - j <= c:
                break
        else:
            appr = appr & set(v)

    ans = list(appr)
    if len(ans) == 0:
        return
    ans.sort()
    for day in ans:
        print(day + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

input()
s = input()
x = []
for ele in s:
    x.append(ele)
for ele in s:
    x.append(ele)
print(x)

Submission status: Wrong Answer

Solution code:
N,K,C = map(int, input().split(' '))
S = input()
ans = []
s =  [i for i, x in enumerate(S) if x == "o"]
for i in s:
  p = 0
  su = 0
  
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()

def solve():
    N, K, C = iip(False)
    S = [1 if i == "o" else 0 for i in input()]

    S.reverse()
    nokori_can_work = []
    nokori_delay = 0
    cur = 0
    for i in S:
        if i and nokori_delay <= 0:
            cur += 1
            nokori_delay = C
        else:
            nokori_delay -= 1
        nokori_can_work.append(cur)
    S.reverse()
    nokori_can_work.reverse()

    max_work = []
    deley_max_work = []
    cur = 0
    nokori_delay = 0
    for i in S:
        if i and nokori_delay == 0:
            cur += 1
            nokori_delay = C
        elif nokori_delay > 0:
            nokori_delay -=1
        max_work.append(cur)
        deley_max_work.append(nokori_delay)

    kouho = []
    for i in range(N):
        if i >= 1 and deley_max_work[i-1] != 0: #maxworkのときに働けるか判定
            continue
        if S[i] == 0:
            continue

        if i == 0:
            max_worked = 0
        else:
            max_worked = max_work[i-1]

        if i + C + 1 > N-1:
            nokori_canworkday = 0
        else:
            nokori_canworkday = nokori_can_work[i+C+1]

        if max_worked + nokori_canworkday + 1 == K:
            if i + C + 1 > N-1:
                if 1 in S[i+1:]:
                    continue

            flag = False
            for j in range(i+1, min((i+C), N)):
                if j+C+1 > N-1:
                    nk2 = 0
                else:
                    nk2 = nokori_can_work[j+C+1]

                if S[j] == 1:
                    if nk2 == nokori_canworkday:
                        flag = True
                        break
                    else:
                        flag = False
                        break

            if not flag:
                kouho.append(i+1)

    #print(S)
    #print(nokori_can_work)
    #print(max_work)
    #print(deley_max_work)
    split_print_enter(kouho)


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_=mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
input()
s = input()
x= []
for ele in s:
  x.append(ele)
print(x)

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)
    for l in ls:
        if len(l) == 1:
            print(l[0])

Submission status: Wrong Answer

Solution code:
N,K,C = map(int, input().split(' '))
S = input()
ans = []
s =  [i for i, x in enumerate(S) if x == "o"]
for i in 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 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.diff(v, n= 1)
  if all(k > C) == True:
    if V == 0:
      V = set(v)
    else:
      V = V  & set(v)
list(V).sort()
print(*V)

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()

if C == 0:
  if W[-1] == K:
    for i in range(N):
      if S[i] == o:
        print(i + 1)
  exit()

DP = [0] * (N + 1)
for i in range(N):
  k = 0
  k += BDP[i]
  if i + C < N:
    k += ADP[i + C]
  if k >= K:
    DP[max(i, -1)] += 1
    DP[min(i + C, N)] -= 1

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

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
ans = []
while i >= 0:
    if t[i] == 1:
        cnt += 1
        for j in range(max(0,i-c),i):
            if t[j] == 1:
                break
        else:
            ans.append(i+1)
        i -= c+1
        continue
    i -= 1

if cnt > k:
    quit()

tmp = ans[-1] 
for i in ans[::-1]:
    print(i)    

cnt = 0
idx = -1
for i in range(tmp+c,n):
    if t[i] == 1:
        cnt += 1
        idx = i
if cnt == 1:
    print(idx+1)

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

    ret = []
    counted = 0

    while isec:
        go = set()
        mi = min(isec)
        i = mi + 1
        while i < n:
            if s[i] == 'o':
                go.add(i)
                if len(go) == k - counted:
                    break
                i += c + 1
            else:
                i += 1

        if len(go) < k - counted:
            ret.append(mi)
            isec.discard(mi)
            counted += 1
        else:
            isec &= go

    print(*map(lambda x: x + 1, ret), 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 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)
# print(lst)
if len(lst) <= K:
    for i, l in enumerate(lst):
        if len(l) == 1:
            print(l[0])
        elif i+1 < K:
            if l[1]+C >= lst[i+1][-1]:
                print(l[0])
else:
    print()

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
ans = []
while i >= 0:
    if t[i] == 1:
        cnt += 1
        for j in range(max(0,i-c),i):
            if t[j] == 1:
                break
        else:
            ans.append(i+1)
        i -= c+1
        continue
    i -= 1

if cnt > k:
    print('')
    quit()
tmp = ans[-1] 
for i in ans[::-1]:
    print(i)    

cnt = 0
idx = -1
for i in range(tmp+c,n):
    if t[i] == 1:
        cnt += 1
        idx = i
if cnt == 1:
    print(idx+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k,c=map(int,input().split())
S=input()

d=deque()
for i in range(n):
  if S[i]=='o':
    d.append([i])
ans=[]
while len(d)>0:
  tmp=d.pop()
  now=tmp[-1]
  for i in range(now+c+1,n):
    if S[i]=='o':
      if len(tmp+[i])==k:
        ans.append(tmp+[i])
      else:
        d.append(tmp+[i])
cnt=[0]*n
for a in ans:
  for tmp in a:
    cnt[tmp]+=1
out=[]
if len(ans)==0:
  exit()
for i,c in enumerate(cnt):
  if c==len(ans):
    out.append(i+1)
print(*out,sep='\n')

Submission status: Wrong Answer

Solution code:
import itertools


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

    if c == 0:
        return

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

    ans = list(ans)
    ans.sort()
    print('\n'.join(str(x + 1) for x in ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

N, K, C = map(int, input().split())
S = input()[::-1]
indices = []
last_set = []
flag = True
pre = 0
for i, s in enumerate(S):
  if i > pre + C:
    flag = True
  if s == 'o':
    indices.append(N-i)
    if flag and K>0:
      last_set.append(N-i)
      K -= 1
      flag = False
      pre = i

ans = []
last_set = last_set[::-1]
indices = indices[::-1]
pre = -1000000
for idx in last_set:
  i = bisect.bisect_left(indices, idx)
  if i == 0:
    ans.append(idx)
    pre = idx
  else:
    ii = indices[i-1]
    if ii - pre <= C:
      ans.append(idx)
      pre = idx
    else:
      pre = ii


for day in ans:
  print(day)

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
            x = bisect.bisect_left(forward, q)
            if x != len(forward) and forward[x] == q:
                res.append(q)
        if cnt == K:
            break
    
    for r in reversed(res):
        print(r)


if __name__ == '__main__':
    main()

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)
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]

l = 0
for item in chuncks:
	if len(item) > 0:
		l += 1 

if l > k:
	pass
else:
	for i in range(len(chuncks)):
		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()

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)
    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)
    for l in ls:
        if len(l) == 1:
            print(l[0])

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, l in enumerate(lst):
        if len(l) == 1:
            print(l[0])
        elif i+1 < K:
            if l[1]+C >= lst[i+1][-1]:
                print(l[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k,c=map(int,input().split())
S=input()

d=deque()
for i in range(n):
  if S[i]=='o':
    d.append([i])
ans=[]
while len(d)>0:
  tmp=d.pop()
  now=tmp[-1]
  for i in range(now+c+1,n):
    if S[i]=='o':
      if len(tmp+[i])==k:
        ans.append(tmp+[i])
      else:
        d.append(tmp+[i])
cnt=[0]*n
for a in ans:
  for tmp in a:
    cnt[tmp]+=1
maxi=max(cnt)
if maxi==0:
  exit()
out=[]
for i,c in enumerate(cnt):
  if c==maxi:
    out.append(i+1)
print(*out,sep='\n')

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

    ret = []

    while isec:
        go = set()
        mi = min(isec)
        i = mi + 1
        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:
            ret.append(mi)
            isec.discard(mi)
        else:
            isec &= go

    print(*map(lambda x: x + 1, ret), 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:
n, k, c = map(int, input().split())
s = list(input())
cnt = s.count('o')
os = [i for i,x in enumerate(s) if x=='o']

from itertools import combinations

ans = []
for x in combinations(os, k):
    b = [x[i+1] - x[i] for i in range(k-1)]
    if len(b)>0 and min(b) > c:
        ans.append(set(x))
    else:
        pass

cnt2 = len(ans)

if cnt2 > 0:
    ans2 = ans[0]
    for i in range(1, cnt2):
        ans2 = ans2 & ans[i]

    for x in ans2:
        print(str(x+1))

else:
    print()

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)
    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()

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:
from sys import stdin
def main():
    input = stdin.readline
    n, k, c = map(int, input().split())
    s = input()

    ans = ""
    for i in range(n):
        if s[i] == "x":
            continue

        cur = 0
        count = 0
        ss = s[cur]

        while cur < n:
            if ss == "o" and cur != i:
                count += 1
                cur += c

            cur += 1

            if count >= k:
                break

        if count < k:
            ans+=str(i+1)+"\n"

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,k,c = map(int,input().split())
s = input()
idx = []
for i in range(n):
    if s[i]=='o':
        idx.append(i+1)
dic = {}
for i in idx:
    dic[i] = 0
cnt = 0
for l in combinations(idx, k):
    l = list(l)
    flg = True
    for j in range(1, len(l)):
        if l[j]-l[j-1]<=c:
            flg = False
    if flg:
        cnt += 1
        for x in l:
            dic[x] = dic[x] + 1
for k,v in dic.items():
    if v==cnt:
        print(k)

Submission status: Wrong Answer

Solution code:
def main():
    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)
            
if __name__ == '__main__':
    main()