Problem: 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.

Submission attempts (in order):
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)



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]

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



Verdicts: Wrong Answer

Accepted