Problem:


Score : 500 points

Problem Statement

Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.

You are given an integer C and a string S. Takahashi will choose his workdays as follows:

After working for a day, he will refrain from working on the subsequent C days.

If the i-th character of S is x, he will not work on Day i, where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.

Find all days on which Takahashi is bound to work.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq N

0 \leq C \leq N

The length of S is N.

Each character of S is o or x.

Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.

Input

Input is given from Standard Input in the following format:

N K C
S

Output

Print all days on which Takahashi is bound to work in ascending order, one per line.

Sample Input 1

11 3 2
ooxxxoxxxoo

Sample Output 1

6

Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.

There are four possible choices for his workdays: Day 1,6,10, Day 1,6,11, Day 2,6,10, and Day 2,6,11.

Thus, he is bound to work on Day 6.

Sample Input 2

5 2 3
ooxoo

Sample Output 2

1
5

There is only one possible choice for his workdays: Day 1,5.

Sample Input 3

5 1 0
ooooo

Sample Output 3

There may be no days on which he is bound to work.

Sample Input 4

16 4 3
ooxxoxoxxxoxoxxo

Sample Output 4

11
16



Sample input:
11 3 2
ooxxxoxxxoo


Sample output:
6

Submission status: Wrong Answer

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

W = [0] * N

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

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

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

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

BDP = [0] + BDP

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


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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

    
for i in range(n):
    if s[i] == 'o':
        if i<c:
            dp[i+1] = 1
        else:
            dp[i+1] = dp[i-c]+1
    else:
        dp[i+1] = dp[i]
dp1 = [0]*(n+1)
for i in range(n)[::-1]:
    if s[i] == 'o':
        dp1[i] = 1 if i+c>=n else dp1[i+c+1]+1
    else:
        dp1[i] = dp1[i+1]
for i in range(n):
    if s[i] == 'x' or not flag[i]:
        continue
    res = 0
    if nxt[i] == -1:
        res = dp[i-1]
    else:
        res = 0 if i-c-1<0 else dp[i-c]
        res += dp1[nxt[i]]
    if res<k:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, k, c = nm()
s = ns()
g = [0]*n
f = [0]*(k+1)
h = [0]*(k+1)
_h = 0
for i in reversed(range(n)):
    if i + c + 1 < n:
        if _h < g[i+c+1]:
            _h = g[i+c+1]
    if s[i] == 'o':
        g[i] = _h + 1
# print(g)

if g[0] == k:
    f = [0]*(k+1)
    h = [0]*(k+1)
    for i in range(n):
        h[g[i]] += 1
    idx = 0
    while idx < n:
        f[g[idx]] += 1
        if g[idx] and h[g[idx]] == 1:
            idx += c
        idx += 1
    # print(f)
    idx = 0
    while idx < n:
        if g[idx] and f[g[idx]] == 1:
            print(idx+1)
            idx += c
        idx += 1

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,K,C = map(int,input().split())
S = input()
def solve():
    l = []
    y = 0
    for i,c in enumerate(S):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            l.append(i+1)
            if len(l) == K:
                break
    r = []
    y = 0
    for i,c in enumerate(S[::-1]):
        if y:
            y -= 1
            continue
        if c=='o':
            y = C
            r.append(N-i)
            if len(r) == K:
                break

    ans = set(l) & set(r)
    print(*sorted(ans), sep='\n')
solve()

Submission status: Wrong Answer

Solution code:
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    #print(need)
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        # 点の数、スタートの点、有向グラフ
        W = [""] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    N, K, C = LI()
    S = SI()
    L = set()
    R = set()
    prev = -inf
    for i,s in enumerate(S):
        if s=="x":
            continue
        if prev+C>=i:
            continue
        L.add(i)
        prev = i
    if len(L)>K:
        print()
        return
    prev = inf
    for i in range(N)[::-1]:
        s = S[i]
        if s=="x":
            continue
        if prev-C<=i:
            continue
        R.add(i)
        prev = i
    #print(L,R)
    ans = []
    for i in L:
        if i in R:
            ans.append(i+1)
    if not ans:
        print()
        return
    for v in ans:
        print(v)
    return

def examF():
    N = I()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    #print(need)
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        # 点の数、スタートの点、有向グラフ
        W = [""] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    N, K, C = LI()
    S = SI()
    L = set()
    R = set()
    prev = -inf
    for i,s in enumerate(S):
        if s=="x":
            continue
        if prev+C>=i:
            continue
        L.add(i)
        prev = i
    if len(L)>K:
        print()
        return
    prev = inf
    for i in range(N)[::-1]:
        s = S[i]
        if s=="x":
            continue
        if prev-C<=i:
            continue
        R.add(i)
        prev = i
    #print(L,R)
    ans = []
    for i in L:
        if i in R:
            ans.append(i+1)
    for v in ans:
        print(v)
    return

def examF():
    N = I()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys
N, K, C = map(int, sys.stdin.readline().split())
S = sys.stdin.readline()
li = []
i = 0
while i < N:
  if S[i] == 'o':
    li.append(i)
  i += 1

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)

if len(ansl) > k:
    print()
    exit()
# 後貪欲
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 a in list(set(ansl) & set(ansl2)):
    print(a+1)

Submission status: Wrong Answer

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, k, c = LI()
    s = S()
    ans = [inf]
    tmp = -inf
    for i in range(n - 1, -1, -1):
        if ans[-1] - c > i and s[i] == "o":
            ans.append(i)
            if len(ans) > k:
                break
    ans.remove(inf)
    ans.sort()
    if len(ans) != k:
        return
    t_ans = [0] * n
    for i in range(n):
        if s[i] == "o" and tmp + k <= i:
            tmp = i
            t_ans[i] = t_ans[i - 1] + 1
        else:
            t_ans[i] = t_ans[i - 1]
    tt = []
    tmp = 0
    for tmp, ai in enumerate(ans):
        if ai == 0:
            tt.append(str(ai + 1))
        if t_ans[ai-1] == tmp:
            tt.append(str(ai + 1))
    print("\n".join(tt))




    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N,K,C=map(int,input().split())
S=input()
L=list()
i=0
nisu=0
while True:
  if i>=N:
    break
  if S[i]=="o":
    L.append(i)
    i+=C+1
    nisu+=1
  else:
    i+=1
if nisu>K:
  exit()
ans=[i for i in L]
for k in range(len(L)):
  i=L[k]+1
  nisu=k
  R=list(L[:k])
  while True:
    if i>=N:
      break
    if S[i]=="o":
      R.append(i)
      i+=C+1
      nisu+=1
    else:
      i+=1
  if len(R)==K:
    ans=set(ans)&set(R)
for i in ans:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()[::-1]
  
  R=[0]*K
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R[k]=(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 in R:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  L,R=[0]*K,[0]*K
  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[k]=N-n
      k+=1
      n += C
    n+=1

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, k, offset=0, 0, 0
  while k < K:
    if n >= offset and S[n]=='o':
      L.append(n+1)
      k+=1
      offset = n + C + 1
    n+=1
  S_Reversed=S[::-1]
  n, k, offset=0, 0, 0
  while k < K:
    if n >= offset and S_Reversed[n]=='o':
      R.append(N - n)
      k+=1
      offset = n + C + 1
    n+=1
  
  
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  N, K, C=map(int, input().split())
  S = input()
  L,R=[],[]
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, k, offset=0, 0, 0
  while k < K:
    if O[n] >= offset:
      L.append(O[n])
      k+=1
      offset = O[n] + C + 1
    n+=1

  n, k, offset=len(O)-1, -1, N
  while k < K and n>=0:
    if O[n] <= offset:
      R.append(O[n])
      k+=1
      offset = O[n] - C - 1
    n-=1
  
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  N, K, C=map(int, input().split())
  S = input()
  O = [int(x)+1 for x, v in enumerate(list(S)) if v=='o'] 
  L,R=[],[]
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  Sr = S[::-1]
  L,R=[],[]
  offset=offsetr=0
  for k in range(K):
    idx=S.find('o',offset)
    idxr=Sr.find('o',offsetr)
    L.append(idx+1)
    R.append(N-idxr)
    offset=idx+C+1
    offsetr=idxr+C+1
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K,C=mi()
    S=list(input())
    ok,ng = "o","x"

    OK = []
    for i in range(N):
        if S[i] == ok:
            OK.append(i+1) # 1-index
    
    greeds = [OK[0]]
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)

    inv_greeds = [OK[-1]]
    for i in range(1,len(OK)):
        x = OK[::-1][i]
        if -x + inv_greeds[-1] > C:
            inv_greeds.append(x)
    
    if len(greeds) < K or len(inv_greeds) < K:
        exit()

    greeds = greeds[:K]
    inv_greeds = inv_greeds[:K][::-1]

    # print(greeds,inv_greeds)
    for i in range(len(greeds)):
        if greeds[i] == inv_greeds[i]:
            print(greeds[i])



    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class SuperArray:
    def __init__(self,init_array=[]):
        self.arr = init_array
        self.se = set(init_array)
    
    def __getitem__(self, item):
        return self.arr[item]

    def append(self,x):
        self.arr.append(x)
        self.se.add(x)
    
    def remove(self,x):
        self.arr.remove(x)
        self.se.remove(x)
    
    def array(self):
        return self.arr
    
    def set(self):
        return self.se


INF=10**20
def main():
    N,K,C=mi()
    S=list(input())
    ok,ng = "o","x"

    OK = []
    for i in range(N):
        if S[i] == ok:
            OK.append(i+1) # 1-index
    
    greeds = [OK[0]]
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)

    inv_greeds = [OK[-1]]
    for i in range(1,len(OK)):
        x = OK[::-1][i]
        if -x + inv_greeds[-1] > C:
            inv_greeds.append(x)
    
    greeds  = greeds[:K]
    inv_greeds = inv_greeds[:K][::-1]

    # print(greeds,inv_greeds)
    for i in range(len(greeds)):
        if greeds[i] == inv_greeds[i]:
            print(greeds[i])



    




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import math
from collections import Counter

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

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

    if S.count('o') < K:
        print('')
        exit()

    WC=[]
    for iter in itertools.combinations(W,K):
        chk = 0
        for i in range(K-1):
            if iter[i+1] - iter[i] <= C:
                chk = 1
                break
        if chk == 0:
            WC.append(iter)

    ans=[]
    if len(WC) == 0:
        print('')
        exit()
    num = len(WC)
    WCC=list(itertools.chain.from_iterable(WC))
    chk1 = Counter(WCC)
    chk2 = list(set(WCC))

    for i in range(len(chk2)):
        if num == chk1[(chk2[i])]:
            ans.append(chk2[i]+1)
    for i in range(len(ans)):
        print(ans[i])

OK()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import math
from collections import Counter

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

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

    if S.count('o') < K:
        print('')
        exit()

    WC=[]
    for iter in itertools.combinations(W,K):
        chk = 0
        for i in range(K-1):
            if iter[i+1] - iter[i] <= C:
                chk = 1
                break
        if chk == 0:
            WC.append(iter)

    ans=[]
    if len(WC) == 0:
        print('')
        exit()

    for i in range(len(WC[0])):
        flg = 0
        for j in range(1,len(WC)):
            for k in range(len(WC[j])):
                if WC[0][i] == WC[j][k]:
                    break
                elif WC[0][i] < WC[j][k]:
                    flg = 1
                    break
            if flg == 1:
                break
        if flg == 0:
            ans.append(WC[0][i]+1)

    if len(ans)==0:
        print('')
    else:
        print(*ans)

OK()

Submission status: Time Limit Exceeded

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

l = [0] * k
l2 = [0] * k

cnt = 0
cnt2 = k - 1
last_work = -1e6
future_work = 1e6

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

    if s[n-i] == 'o' and future_work - (n-i+1) > c:
        l2[cnt2] = (n-i+1)
        cnt2 -= 1
        future_work = (n-i+1)
                
for i in l:
    if i in l2:
        print(i)

Submission status: Time Limit Exceeded

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

l = [0] * k
l2 = [0] * k

cnt = 0
cnt2 = k - 1
last_work = -1e6
future_work = 1e6

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

    if cnt2 != -1:
        if s[n-i] == 'o':
            if future_work - (n-i+1) > c:
                l2[cnt2] = (n-i+1)
                cnt2 -= 1
                future_work = (n-i+1)
                
for i in l:
    if i in l2:
        print(i)

Submission status: Time Limit Exceeded

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, 0, -1):
    if cnt == -1:
        break
    if s[i-1] == 'x':
        continue
    if future_work - i > c:
        l2[cnt] = i
        cnt -= 1
        future_work = i

for i in l:
    if i in l2:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    Left=[]
    Right=[]

    counter=0
    while counter<N and len(Left)<K:
        if S[counter]=="o":
            if len(Left)<K:
                Left.append(counter)
                counter+=C
        counter+=1

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.insert(0,counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        if Right[i]==Left[i]:
            print(Right[i]+1)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, K, C = nm()
S = ns()
assert len(S) == N

INF = 1 << 60


def solve():
    lfilled = [0] * N  # max left count where i-th position is filled
    lempty = [0] * N  # max left count where i-th position is empty
    for i in range(0, N):
        if i > 0:
            lempty[i] = max(lempty[i - 1], lfilled[i - 1])
        if S[i] == "x":
            lfilled[i] = -INF
        elif i - C >= 0:
            lfilled[i] = lempty[i - C] + 1
        else:
            lfilled[i] = 1

    rfilled = [0] * N
    rempty = [0] * N
    for i in range(N - 1, -1, -1):
        if i < N - 1:
            rempty[i] = max(rempty[i + 1], rfilled[i + 1])
        if S[i] == "x":
            rfilled[i] = -INF
        elif i + C < N:
            rfilled[i] = rempty[i + C] + 1
        else:
            rfilled[i] = 1

    def must_work(s, t):
        l = max(lfilled[s - 1], lempty[s - 1]) if s - 1 >= 0 else 0
        r = max(rfilled[t], rempty[t]) if t < N else 0
        # print(f"day {s}-{t}: l+r={l+r} l={l} r={r}", file=sys.stderr)
        return l + r < K

    no_need_to_work = set()
    for i in range(1 - C, N):
        if not must_work(i, i + C):
            for j in range(i, i + C):
                no_need_to_work.add(j)

    ans = set(range(N)) - no_need_to_work
    return [x + 1 for x in sorted(ans)]


def solve0():
    workable = [i + 1 for i, x in enumerate(S) if x == "o"]
    if len(workable) == K:
        return workable
    assert len(workable) > K
    return []


if C == 0:
    print(*solve0(), sep="\n")
else:
    print(*solve(), sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = list(input())
left = [0]*n
right = [0]*n
s_r = list(reversed(s))

count_l=1
count_r=1
i=j=0
while i<n or j<n:
    
    if i >= n:
        i=n
    else:
        if s[i] == 'o':
            left[i] = count_l
            count_l+=1
            i+=c+1
        else:
            i+=1
            
    if j >= n:
        j=n
    else:    
        if s_r[j] == 'o':
            right[j] = count_r
            count_r += 1
            j+=c+1
        else:
            j+=1
    
right.reverse()
need=[]
for i in range(n):
    if s[i] != 'o':
        continue
    else:
        j=h=0
        cl=cr=0
        cl_i=-c
        cr_i=n+c
        if i!=0:
            while i-j>=1:
                j+=1
                if left[i-j] != 0:
                    cl = left[i-j]
                    cl_i = i-j
                    break
     
        
        if i!=n-1:
            while i+h <= n-2:
                h+=1
                if right[i+h] != 0:
                    cr = right[i+h]
                    cr_i = i+h
                    break
    
    if cr_i-cl_i<=c:
        co = cr+cl-1
        
    else:
        co = cr+cl

    if co<k:
        need.append(str(i+1))


print('\n'.join(need))

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = list(input())
left = [0]*n
right = [0]*n
s_r = list(reversed(s))

count_l=1
count_r=1
i=j=0
while i<n or j<n:
    
    if i >= n:
        i=n
    else:
        if s[i] == 'o':
            left[i] = count_l
            count_l+=1
            i+=c+1
        else:
            i+=1
            
    if j >= n:
        j=n
    else:    
        if s_r[j] == 'o':
            right[j] = count_r
            count_r += 1
            j+=c+1
        else:
            j+=1
    
right.reverse()
need=[]
for i in range(n):
    if s[i] != 'o':
        continue
    else:
        j=h=1
        cl=cr=0
        if i!=0:
            if sum(left[:i])==0:
                cl_i=-c
            else:
                while i-j>=0:
                    
                    if left[i-j] != 0:
                        cl = left[i-j]
                        cl_i = i-j
                        break
                    j+=1
        else:
            cl_i=-c
    
        if i!=n-1:
            if sum(right[i:])==0:
                cr_i=n+c
            else:
                while i+h <= n-1:
                    
                    if right[i+h] != 0:
                        cr = right[i+h]
                        cr_i = i+h
                        break
                    h+=1
                    
        else:
            cr_i=n+c
    if cr_i-cl_i<=c:
        co = cr+cl-1
        
    else:
        co = cr+cl

    if co<k:
        need.append(str(i+1))


print('\n'.join(need))

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = list(input())
left = [0]*n
right = [0]*n
s_r = list(reversed(s))

count_l=1
count_r=1
i=j=0
while i<n or j<n:
    
    if i >= n:
        i=n
    else:
        if s[i] == 'o':
            left[i] = count_l
            count_l+=1
            i+=c+1
        else:
            i+=1
            
    if j >= n:
        j=n
    else:    
        if s_r[j] == 'o':
            right[j] = count_r
            count_r += 1
            j+=c+1
        else:
            j+=1
    
right.reverse()
need=[]
for i in range(n):
    if s[i] != 'o':
        continue
    else:
        j=h=1
        cl=cr=0
        if i!=0:
            if sum(left[:i])==0:
                cl_i=-c
            else:
                while i-j>=0:
                    
                    if left[i-j] != 0:
                        cl = left[i-j]
                        cl_i = i-j
                        break
                    j+=1
        else:
            cl_i=-c
    
        if i!=n-1:
            if sum(right[i:])==0:
                cr_i=n+c
            else:
                while i+h <= n-1:
                    
                    if right[i+h] != 0:
                        cr = right[i+h]
                        cr_i = i+h
                        break
                
                    h+=1
        else:
            cr_i=n+c
    if cr_i-cl_i<=c:
        co = cr+cl-1
        
    else:
        co = cr+cl

    if co<k:
        need.append(str(i+1))


print('\n'.join(need))