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
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K, C = mapint()
S = list(input())
r_S = S[::-1]

pos = [0]*N
neg = [0]*N
ok = 0
cnt = 0
for i in range(N):
    if S[i]=='o':
        if ok<=i:
            pos[i] = cnt + 1
            cnt += 1
            ok = i + C + 1

    else:
        pass
ok = 0
cnt = 0
for i in range(N):
    if r_S[i]=='o':
        if ok<=i:
            neg[i] = cnt + 1
            cnt += 1
            ok = i + C + 1

    else:
        pass

ans = []
neg = neg[::-1]
for i in range(N):
    if pos[i]+neg[i]-1==K:
        ans.append(i)
for a in ans:
    print(a+1)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
N日間のうちK日選んで働く
働いたらそれからC日間は働かない
Sにxがついていたら働かない

oの付いてる日のみ働く
全ての通りを求めてみよう

N, K, C = 11, 3, 2
S = ooxxxoxxxoo の時
働けるのは[1, 2, 6, 10, 11]日目
ここから3つ以上間が空く条件で3つ選ぶと条件を満たす
全ての通りでi日目に働く必要がある

A = [1, 2, 5, 7, 11, 13, 16]
M = 4
C = 3

for bit in range(1 << len(A)):
    cnt = []
    for i in range(len(A)):
        if bit & (1 << i):
            cnt.append(A[i])
    if len(cnt) == 4:
        for i in range(1, len(cnt)):
            if cnt[i] - cnt[i - 1] <= C:
                break
        else:
            print(cnt)

# python index.py
[1, 5, 11, 16]
[1, 7, 11, 16]
[2, 7, 11, 16]

A = [1, 2, 5, 10, 24]
M = 3
C = 2
[1, 5, 10]
[2, 5, 10]
[1, 5, 24]
[2, 5, 24]
[1, 10, 24]
[2, 10, 24]
[5, 10, 24]
[1, 5, 10, 24] M + 1回以上ジャンプできる場合には答えが[]になる
A[0]から頑張ってもM回しかジャンプできない

間がC + 1以上離れたM個の集合はどのように求める？
必ず働く日の特性は？
動かすと？
場所は固定？
"""
# N, K, C = getNM()
# S = getN()

N, K, C = getNM()
S = input()

# i回目に選べる要素の上限と下限を比べる
place = []
for i in range(N):
    if S[i] == 'o':
        place.append(i)

# 下限 出来るだけ前の仕事を選べるように
fore = [place[0]]
for i in place[1:]:
    if i - fore[-1] > C:
        fore.append(i)

# 上限 出来るだけ後ろの仕事を選ぶように
back = deque([])
back.append(place[-1])
for i in place[::-1]:
    if back[0] - i > C:
        back.appendleft(i)
back = list(back)

ans = []
for a, b in zip(fore, back):
    if a == b:
        ans.append(a + 1)

for i in ans:
    print(i)


"""
fore = [0] * N
if S[0] == 'o':
    fore[0] = 1

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

back = [float('inf')] * N
ma = max(fore)
if S[N - 1] == 'o':
    back[N - 1] = ma

for i in range(N - 2, -1, -1):
    back[i] = min(ma, back[i + 1])
    if S[i] == 'o' and i + C + 1 < N:
        back[i] = min(back[i], back[i + C + 1] - 1)
print(back)
"""

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
N日間のうちK日選んで働く
働いたらそれからC日間は働かない
Sにxがついていたら働かない

oの付いてる日のみ働く
全ての通りを求めてみよう

N, K, C = 11, 3, 2
S = ooxxxoxxxoo の時
働けるのは[1, 2, 6, 10, 11]日目
ここから3つ以上間が空く条件で3つ選ぶと条件を満たす
全ての通りでi日目に働く必要がある

A = [1, 2, 5, 7, 11, 13, 16]
M = 4
C = 3

for bit in range(1 << len(A)):
    cnt = []
    for i in range(len(A)):
        if bit & (1 << i):
            cnt.append(A[i])
    if len(cnt) == 4:
        for i in range(1, len(cnt)):
            if cnt[i] - cnt[i - 1] <= C:
                break
        else:
            print(cnt)

# python index.py
[1, 5, 11, 16]
[1, 7, 11, 16]
[2, 7, 11, 16]

A = [1, 2, 5, 10, 24]
M = 3
C = 2
[1, 5, 10]
[2, 5, 10]
[1, 5, 24]
[2, 5, 24]
[1, 10, 24]
[2, 10, 24]
[5, 10, 24]
[1, 5, 10, 24] M + 1回以上ジャンプできる場合には答えが[]になる
A[0]から頑張ってもM回しかジャンプできない

間がC + 1以上離れたM個の集合はどのように求める？
必ず働く日の特性は？
動かすと？
場所は固定？

block[0]からC以内の数字でblockを作る
blockがMでなければ（多い/足りない）なら答えは[]

11 3 2
ooxxxoxxxoo
[[0, 1], [5], [9, 10]]
"""
# N, K, C = getNM()
# S = getN()

N, K, C = getNM()
S = input()
place = []
for i in range(N):
    if S[i] == 'o':
        place.append(i)

block = []
now = [place[0]]

for i in place[1:]:
    if i - now[0] <= C:
        now.append(i)
    else:
        block.append(now)
        now = [i]
block.append(now)

if len(block) != K:
    print()
    exit()

all = [block[K - 1]]
for i in range(K - 2, -1, -1):
    cnt = []
    for j in block[i]:
        if block[i + 1][-1] - j > C:
            cnt.append(j)
    all.append(cnt)

ans = []
for block in all:
    if len(block) == 1:
        ans.append(block[0])

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

Submission status: Wrong Answer

Solution code:
n,k,c = map(int,input().split())
s = input()
canwork=[0]*(n+1) #canwork[i]:=i日目までに働くことができる最大日数(1-indexed)
canwork2 = [0]*(k+n+3)
for i in range(n):
    if s[i] == "o":
        canwork[i+1]=max(canwork[i],canwork[i+1-k]+1)
        
    else:
        canwork[i+1] = canwork[i]
        
for i in range(n)[::-1]:
    if s[i] == "o":
        canwork2[i]=max(canwork2[i+1],canwork2[i+k]+1)
    else:
        canwork2[i] = canwork2[i+1]

ans = []
for i in range(n):
    if canwork[i]+canwork2[i+1]==k-1:
        ans.append(i+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

l_lst=[0]*k
r_lst=[0]*k

l=-2*c
cnt=0
for i in range(n):
    if i-l>c and s[i]!="x":
        l_lst[cnt]=i
        cnt+=1
        l=i
        if cnt==k:
            break
# print(l_lst)
l=n+2*c
cnt=0
for i in range(n)[::-1]:
    if l-i>c and s[i]!="x":
        r_lst[-1-cnt]=i
        cnt+=1
        l=i
        if cnt==k:
            break
# print(r_lst)

for i,j in zip(l_lst,r_lst):
    if i==j:
        print(i+1)

Submission status: Wrong Answer

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()[::-1]
  
  R=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1
  
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if {n+1}&R:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()[::-1]
  
  R=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1
  #print(R)
  R.add(-1)
  
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if set((n+1,))&R:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  
  S=S[::-1]
  R=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1
  #print(R)
  
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 in R:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  L=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      L.add(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  S=S[::-1]
  R=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1
  #print(R)

  for i in sorted(list(L&R)):
    print(i)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  L,R=[0]*K,set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      L[k]=n+1
      k+=1
      n += C
    n+=1
  #print(L)
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1

  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

forward,backward=[0]*N,[0]*N
f_idx,b_idx=0,N-1
f_count,b_count = 1,1
for i in range(N):
  if f_idx<=i and S[i]=='o' and f_count<=K:
    forward[i] = f_count
    f_count += 1
    f_idx = i+C+1
  if b_idx>=N-i-1 and S[-i-1]=='o' and b_count<=K:
    backward[-i-1] = b_count
    b_count += 1
    b_idx = N-i-1-(C+1)

for i in range(N):
  if forward[i] != 0 and backward[i] != 0:
    print(i+1)

Submission status: Wrong Answer

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

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

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

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

	A=[]
	now=0

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

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

	A=set(A)
	B=set(B)
	C=A&B
	C=list(C)
	C.sort()
	print(*C,sep="\n")








if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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

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

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

	A=[]
	now=0

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

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

	A=set(A)
	B=set(B)
	C=A&B
	C=list(C)
	C.sort()
	print(*C,sep="\n")








if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

work = [0] * n

cnt = 0
left = 0

while cnt != k and left < n:
    if s[left] == 'o':
        work[left] += 1
        cnt += 1
        left += c
    left += 1

cnt = 0
right = n - 1
while cnt != k and right >= 0:
    if s[right] == 'o':
        work[right] += 1
        cnt += 1
        right -= c
    right -= 1

print("\n".join(map(str, [i + 1 for i, v in enumerate(work) if v == 2])))

Submission status: Wrong Answer

Solution code:

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

cand = [True] * N

cnt = 0
nex = -1
for i in range(N):
    if S[i] == "o" and i > nex and cnt < K:
        nex = i + C
        cnt += 1
    else:
        cand[i] = False

cnt = 0
nex = N
for i in reversed(range(N)):
    if S[i] == "o" and i < nex and cnt < K:
        nex = i - C
        cnt += 1
    else:
        cand[i] = False

for i in range(N):
    if cand[i]:
        print(i + 1)

Submission status: Wrong Answer

Solution code:

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

cand = [True] * N

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

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

for i in range(N):
    if cand[i]:
        print(i + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

left = set()
right = set()

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

ans = sorted(list(left & right))
for x in ans:
    print(x + 1)

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = input()
left = set()
right = set()
i = 0
while i < n:
    if s[i] == 'o':
        left.add(i)
        i += c
        if len(left) == k:
            break
    i += 1
i = n - 1
while i >= 0:
    if s[i] == 'o':
        right.add(i)
        i -= c
        if len(right) == k:
            break
    i -= 1
for x in left & right:
    print(x + 1)

Submission status: Wrong Answer

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


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

for i in range(n):
    if a[i] and b[i]:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline


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

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


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


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


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


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


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


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


# rstrip().decode('utf-8')
def main():
	n,k,c=MI()
	s=input().rstrip().decode()
	
	kk=k
	i=0
	L=[]
	while kk:
		if s[i]=="o":
			L.append(i+1)
			i+=c+1
			kk-=1
		else:
			i+=1
		
	kk=k
	i=n-1
	R=[]
	while kk:
		if s[i]=="o":
			R.append(i+1)
			i-=c+1
			kk-=1
		else:
			i-=1
	
	LL=set(L)
	RR=set(R)
	LR=LL&RR
	LR=list(LR)
	LR.sort()
	
	print(*LR,sep="\n")
	
	
	
	
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:

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

ok = [True] * N
tmp = 0
cnt = 0
for i in range(N):
    if S[i] == "o" and tmp <= 0 and cnt < K:
        tmp = C
        cnt += 1
    else:
        ok[i] = False
        tmp -= 1

tmp = 0
cnt = 0
for i in reversed(range(N)):
    if S[i] == "o" and tmp <= 0 and cnt < K:
        ok[i] &= True
        tmp = C
        cnt += 1
    else:
        ok[i] = False
        tmp -= 1

for i in range(N):
    if ok[i]:
        print(i + 1)

Submission status: Wrong Answer

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

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

print(* sorted(list(s & s2)), sep='\n')

Submission status: Wrong Answer

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

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

print(* sorted(list(s & s2)), sep='\n')

Submission status: Wrong Answer

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

s = set()
prev = -C
for i in range(N):
    if len(s) == K:
        break
    if prev + C < i+1:
        if S[i] == 'x':
            continue
        else:
            prev = i+1
            s.add(i+1)
s2 = set()
next = N+C
for i in range(N-1, -1, -1):
    if len(s2) == K:
        break
    if next - C > i:
        if S[i] == 'x':
            continue
        else:
            s2.add(i+1)
            next = i

print(* sorted(list(s & s2)), sep='\n')

Submission status: Wrong Answer

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

s = set()
prev = -C
for i in range(N):
    if len(s) == K:
        break
    if prev + C < i+1:
        if S[i] == 'x':
            continue
        else:
            prev = i+1
            s.add(i+1)
s2 = set()
next = N+C
for i in range(N-1, -1, -1):
    if len(s2) == K:
        break
    if next - C > i:
        if S[i] == 'x':
            continue
        else:
            s2.add(i+1)
            next = i

print(*(s & s2), sep='\n')

Submission status: Wrong Answer

Solution code:
n,k,c=map(int,input().split())
s=input()
sj=[0]*n
sg=[0]*n
cnt=1
i=0
while i<n:
    if s[i]=="o":
        sj[i]=cnt
        cnt+=1
        i+=c
    if cnt==k+1:
        break
    i+=1

cnt=k
i=n-1
while i>-1:
    if s[i]=="o":
        sg[i]=cnt
        cnt-=1
        i-=c
    if cnt==0:
        break
    i-=1
flag=True
for i in range(n):
    if s[i]=="o" and sj[i]>0 and sg[i]>0:
        flag=False
        print(i+1)
if flag:
    print("")

Submission status: Wrong Answer

Solution code:
n,k,c=map(int,input().split())
s=input()
sj=[0]*n
sg=[0]*n
cnt=1
i=0
while i<n:
    if s[i]=="o":
        sj[i]=cnt
        cnt+=1
        i+=c
    if cnt==k+1:
        break
    i+=1

cnt=k
i=n-1
while i>-1:
    if s[i]=="o":
        sg[i]=cnt
        cnt-=1
        i-=c
    if cnt==0:
        break
    i-=1
for i in range(n):
    if s[i]=="o" and sj[i]>0 and sg[i]>0:
        print(i+1)

Submission status: Wrong Answer

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

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

out = set(L) & set(R)
out = list(out)
out.sort()
for a in out:
    print(a+1)

Submission status: Wrong Answer

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

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

out = set(L) & set(R)
for a in out:
    print(a+1)

Submission status: Wrong Answer

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

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

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

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

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

main()

Submission status: Wrong Answer

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

l = [0] * k
cnt = 0
last_work = -1e6

for i in range(1, n+1):
    if cnt == k:
        break
    if s[i-1] == 'x':
        continue
    if i - last_work > c:
        l[cnt] = i
        cnt += 1
        last_work = i

l2 = [0] * k
cnt = k - 1
future_work = 1e6
for i in range(n, 1, -1):
    if cnt == -1:
        break
    if s[i-1] == 'x':
        continue
    if future_work - i > c:
        l2[cnt] = i
        cnt -= 1
        future_work = i

cnt = 0
for i in l:
    if i in l2:
        cnt += 1
if cnt > 0:
    print(cnt)

Submission status: Wrong Answer

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

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

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

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

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

    def __len__(self):
        return self._len

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

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

        return self._func(res_left, res_right)

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


from collections import defaultdict


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

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


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


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


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

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

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

Submission status: Wrong Answer

Solution code:
class Group:

    def __init__(self, index, pattern):
        self.index = index
        self.pattern = pattern
        # set later
        self.dist_to_next_group = 0
        self.last_ok_index_of_next_group = 0


def main():
    INF = 10 ** 6
    N, K, C = list(map(int, input().split(' ')))
    S = input()
    index = 0
    groups = list()
    while index <= N - 1:
        if S[index] == 'x':
            index += 1
            continue
        groups.append(Group(index, S[index:min(N, index + C + 1)]))
        index += C + 1
    # set dist_to_next_group and last_ok_index_of_next_group
    for i in range(len(groups) - 1):
        groups[i].dist_to_next_group = groups[i + 1].index - groups[i].index
        for j, c in enumerate(groups[i + 1].pattern):
            if c == 'o':
                groups[i].last_ok_index_of_next_group = j
    groups[-1].dist_to_next_group = INF
    groups[-1].last_ok_index_of_next_group = INF
    # check
    if len(groups) > K:
        print('')
        return
    ans = list()
    for group in groups:
        next_ok_index = 0
        for i, c in enumerate(group.pattern):
            if i == 0:
                continue
            if c == 'o':
                next_ok_index = i
                break
        if next_ok_index == 0 or next_ok_index + C >= group.dist_to_next_group + group.last_ok_index_of_next_group:
            ans.append(group.index + 1)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# E - Yutori
N,K,C = map(int,input().split())
S = input()
L = [0]*K
R = [0]*K

i = 0
for j in range(K):
    while S[i]!='o':
        i += 1
    L[j] = i
    i += C+1

i = K-1
for j in range(K-1,-1,-1):
    while S[i]!='o':
        i -= 1
    R[j] = i
    i -= C+1
    
for j in range(K):
    if L[j]==R[j]:
        print(L[j])

Submission status: Wrong Answer

Solution code:
n,k,c=map(int,input().split())
s=input()
l=list();r=list()
nex=0
for i in range(n):
	if i<nex:
		continue
	if s[i]=="o":
		nex=i+c+1
		l.append(i)
nex=-1
for i in range(n):
	if i<nex:
		continue
	if s[-i-1]=="o":
		nex=i+c+1
		r.append(n-i-1)
r=r[::-1]
for i in range(len(l)):
	if l[i]==r[i]:
		print(l[i]+1)

Submission status: Wrong Answer

Solution code:
n,k,c=map(int,input().split())
s=input()
l=set();r=set()
nex=0
for i in range(n):
	if i<nex:
		continue
	if s[i]=="o":
		nex=i+c+1
		l.add(i)
nex=-1
for i in range(n):
	if i<nex:
		continue
	if s[-i-1]=="o":
		nex=i+c+1
		r.add(n-i-1)
K=list(l&r)
if len(K)>k:
	print()
	exit()
for x in K:
	print(x+1)

Submission status: Wrong Answer

Solution code:
exit()

Submission status: Wrong Answer

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

s2 = s[::-1]

dp1 = [0] * (n + 2)
dp2 = [0] * (n + 2)

for (dp, ss) in zip([dp1, dp2], [s, s2]):
    for i in range(n):
        if ss[i] == 'x':
            dp[i+1] = dp[i]
        elif i <= c:
            dp[i+1] = min(1, dp[i] + 1)
        else:
            dp[i+1] = max(dp[i+1-c] + 1, dp[i])

dp2 = dp2[::-1]

for i in range(1, n+1):
    if s[i-1] == 'o' and dp1[i-1] + dp2[i+1] < k:
        print(i)

Submission status: Wrong Answer

Solution code:
n, k, c = map(int, input().split())
s = input()
hidari = set()
migi = set()
cnt = 0
yasumi = -1
for i in range(n):
    if i > yasumi and cnt < k:
        if s[i] == "o":
            hidari.add(i)
            yasumi = i + c
            cnt += 1
cnt = 0
yasumi = n
for i in range(n - 1, -1, -1):
    if cnt < k and i < yasumi:
        if s[i] == "o":
            migi.add(i)
            yasumi = i - (c)
            cnt += 1

ans = hidari & migi
ans = list(ans)
ans.sort()
ans2 = []
for num in ans:
    ans2.append(num + 1)
print(*ans2, sep=" ")