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: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, k, c = [int(s) for s in input().strip().split()]
    s = input().strip()

    if c == 0:
        if s.count("o") == k:
            for i in range(n):
                if s[i] == "o":
                    print(i + 1)
        return

    prefix, suffix = [0] * n, [0] * n
    for i in range(n):
        if s[i] == "o":
            prefix[i] = 1 + (prefix[i - c - 1] if i - c - 1 >= 0 else 0)
        else:
            prefix[i] = prefix[i - 1] if i - 1 >= 0 else 0
    for i in range(n - 1, -1, -1):
        if s[i] == "o":
            suffix[i] = 1 + (suffix[i + c + 1] if i + c + 1 < n else 0)
        else:
            suffix[i] = suffix[i + 1] if i + 1 < n else 0
    
    cont = 0
    for i in range(-c + 1, n):
        ok = (prefix[i - 1] if i - 1 >= 0 else 0) + (suffix[i + c] if i + c < n else 0) >= k
        if ok:
            cont = 0
        else:
            cont += 1
            if cont >= c:
                print(i + 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, K, C = map( int, input().split())
    S = input()
    T = [False]*N
    ANS = [1]*N
    for i in range(N):
        if S[i] == "o":
            T[i] = True
        else:
            ANS[i] = 0
    F = []
    i = 0
    now = 0
    D = [False]*N
    k = 0
    while i < N and k < K:
        if T[i]:
            F.append(i)
            D[i] = True
            i += C+1
            k += 1
        else:
            i += 1
    for i in range(N):
        if not D[i]:
            ANS[i] = 0
    # print(ANS, F)
    end = N-1
    for i in range(N-1,-1,-1):
        if T[i]:
            end = i
            break
    for m in F[::-1]:
        # print(m, end)
        if m < end:
            ANS[m] = 0
        if end == 0:
            break
        for j in range(end-C-1,-1,-1):
            # print(j,T[j])
            if T[j]:
                end = j
                break

    print("\n".join( map( str, [ i+1 for i in range(N) if ANS[i] == 1])))
            
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N, K, C = map(int, input().split())
S = list(input())[: -1]
e = [-1] * N
os = []
for i in range(N):
  if S[i] == "o": os.append(i)
for i in range(N):
  if S[i] == "o":
    j = br(os, i + C)
    if j == len(os): continue
    e[i] = os[j]
#print(e)
dp = [0] * N
for i in range(N - 1, -1, -1):
  if e[i] != -1:
    dp[i] = dp[e[i]] + 1
  else: dp[i] += S[i] == "o"
if max(dp) > K:
  print()
  exit(0)
l = []
r = []
ls = 0
rs = 0
for i in range(N):
  if S[i] == "o":
    ls = i
    break
l.append(ls)

for i in range(N - 1, -1, -1):
  if dp[i] == K:
    rs = i
    break
r.append(rs)
#print(l, r)
for i in range(ls, N):
  if S[i] == "x": continue
  if l[-1] + C < i: l.append(i)
for i in range(rs, N):
  if S[i] == "x": continue
  if r[-1] + C < i: r.append(i)
  elif dp[r[-1]] == dp[i]: r[-1] = i
res = set(l) & set(r)
for r in sorted(res):
  print(r + 1)

Submission status: Accepted

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

memo = [0]*N
f = 0
for i in range(N-1, max(-1, N-C-2), -1):
    if S[i] == "o":
        f = 1
        break
if f == 1:
    for i in range(N-1, max(-1, N-C-2), -1):
        memo[i] = 1
for i in range(max(-1, N-C-2), -1, -1):
    if S[i] == "o":
        memo[i] = memo[i+C+1]+1
    else:
        memo[i] = memo[i+1]

m2 = [0]*N
cnt = 0
i = 0
while i < N:
    if S[i] == "o":
        cnt += 1
        m2[i] = cnt
        i += C+1
    else:
        i += 1
m2[0] = (m2[0], 0)
for i in range(1, N):
    if m2[i] == 0:
        m2[i] = m2[i-1]
    else:
        m2[i] = (m2[i], i)

ans = []
for i in range(1, N-1):
    if S[i] == "x":
        continue
    if m2[i-1][1]+C+1 >= N:
        if m2[i-1][0] < K:
            ans.append(i+1)
    elif m2[i-1][0] + memo[max(m2[i-1][1]+C+1, i+1)] < K:
        ans.append(i+1)

if N > 1:
    if m2[-2][0] < K and S[-1] == "o":
        ans.append(N)
    if memo[1] < K and S[0] == "o":
        ans.append(1)
elif S[0] == "o" and K > 0:
    ans.append(1)
ans.sort()
for a in ans:
    print(a)

Submission status: Accepted

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

if N == 1:
    print(1)
    exit()

before = [[0] * 2 for _ in range(N)]
if S[0] == 'o':
    before[0] = [1, C]
for i in range(1, N):
    before[i] = list(before[i-1])
    if S[i] == 'o' and i > before[i-1][1]:
        before[i][0] += 1
        before[i][1] = i + C

after = [0] * N
end = N
if S[-1] == 'o':
    after[-1] = 1
    end = N - 1 - C
for i in range(N-1)[::-1]:
    after[i] = after[i+1]
    if S[i] == 'o' and i < end:
        after[i] += 1
        end = i - C

if after[1] < K:
    print(1)
for i in range(1, N-1):
    d, s = before[i-1]
    if s < N:
        d += after[max(i+1, s)]
    if d < K:
        print(i + 1)
if before[-2][0] < K:
    print(N)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
sub = []
key = -1
for i in range(n):
  if s[i] == "o" and (key == -1 or key+c+1 <= i):
    sub.append(i+1)
    key = i
  if len(sub) == k:
    break

sub2 = []
key = -1
for i in range(n-1, -1, -1):
  if s[i] == "o" and (key == -1 or key-c-1 >= i):
    sub2.append(i+1)
    key = i
  if len(sub2) == k:
    break

sub2.reverse()
ans = []
for i in range(k):
  if sub[i] == sub2[i]:
    ans.append(sub[i])

for value in ans:
  print(value)

Submission status: Accepted

Solution code:
import bisect
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, K, C = read_values()
    S = input().strip()
    P = []

    c = -1
    for i, s in enumerate(S):
        if s == "o":
            if c == -1:
                c = 0
                L = [i]
            else:
                L.append(i)
        if c == -1:
            continue
        c += 1
        if c > C:
            P.append(L)
            c = -1
    if c != -1:
        P.append(L)

    if len(P) > K:
        return

    t = len(P[-1])
    res = []
    for i in range(len(P) - 1, 0, -1):
        if len(P[i][:t]) == 1:
            res.append(str(P[i][0] + 1))
        
        p = P[i][t - 1]
        t = bisect.bisect_left(P[i - 1], p - C)
    
    if len(P[0][:t]) == 1:
        res.append(str(P[0][0] + 1))

    print("\n".join(res[::-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

forward_schedule = [-1 if c == 'x' else 0 for c in S]
backward_schedule = [-1 if c == 'x' else 0 for c in S]
# forward
i_work = 1
for i in range(N):
  if forward_schedule[i] == -1: continue
  forward_schedule[i] = i_work
  for j in range(1, C+1):
    if i+j < N: forward_schedule[i+j] = -1
  i_work += 1

# backward
i_work = K
for i in range(N-1, -1, -1):
  if backward_schedule[i] == -1: continue
  backward_schedule[i] = i_work
  for j in range(1, C+1):
    if i-j >= 0: backward_schedule[i-j] = -1
  i_work -= 1

for i in range(N):
  if forward_schedule[i] == backward_schedule[i] and forward_schedule[i] > 0:
    print(i+1)

Submission status: Accepted

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

s_len = len(S)
from_begin = set()
from_end = set()
i = 0
while(i < s_len):
    if S[i] == "o":
        from_begin.add(i+1)
        i += C
    i += 1

i = s_len - 1

while(i > -1):
    if S[i] == "o":
        from_end.add(i+1)
        i -= C
    i -= 1

# print(from_begin, from_end)

if len(from_begin) != K or len(from_end) != K:
    exit()
else:
    ans_array = list(from_end & from_begin)
    ans_array.sort()
    print("\n".join(map(str, ans_array)))

Submission status: Accepted

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

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

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    if n == 1:
        print(1)
        return

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None for i in range(n)]
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if N==1:
  print(1)
  exit()

Af = [0]*N
Rf = [0]*N
d = 0
f = 0
for i, s in enumerate(S):
    f-=1
    if s=='o' and f<0:
        d+=1
        f=C
    Af[i]=d
    Rf[i]=C-f

Ab = [0]*N
Rb = [0]*N
d = 0
f = 0
for i, s in enumerate(S[::-1]):
    f-=1
    if s=='o' and f<0:
        d+=1
        f=C
    Ab[N-i-1]=d
    Rb[N-i-1]=C-f

if Ab[1]<K:
    print(1)

for i in range(1, N-1):
    if Af[i-1]+Ab[i+1]>K: continue
    if Af[i-1]+Ab[i+1]==K and Rf[i-1]+Rb[i+1]+1>=C: continue
    print(i+1)

if Af[-2]<K:
    print(N)

Submission status: Accepted

Solution code:
n,k,c = (int(num) for num in input().split())
s = input()
earliest = [0] * k
idx = 0
for i in range(n):
    if s[i] == "o" and (idx == 0 or i - earliest[idx-1] > c):
        earliest[idx] = i
        idx += 1
    if idx >= k:
        break
        
latest = [0] * k
idx = k - 1
for i in range(n-1,0,-1):
    if s[i] == "o" and (idx == k-1 or latest[idx+1] - i > c):
        latest[idx] = i
        idx -= 1
    if idx < 0:
        break
        
#print(earliest)
#print(latest)
        
for i in range(k):
    if earliest[i] == latest[i]:
        print(earliest[i] + 1)

Submission status: Accepted

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


dp1 = [0] * (N + 1)  # iまでで何回働けるか
dp1[0] = 0
for i, s in enumerate(S, start=1):
    if s == 'x':
        dp1[i] = dp1[i - 1]
        continue
    b = max(0, i - C - 1)
    dp1[i] = dp1[b] + 1


dp2 = [0] * (N + 1)  # i以降で何回働けるか
for i in reversed(range(N)):
    s = S[i]
    if s == 'x':
        dp2[i] = dp2[i + 1]
        continue
    b = min(N, i + C + 1)
    dp2[i] = dp2[b] + 1


ans = []
# i番目のやつを使わなくてもK個取れるか？
for i in range(1, N + 1):
    if dp1[i - 1] + dp2[i] < K:
        ans.append(i)

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def solve(n, k, c, s):
    ls = set()
    lp = -c - 1
    lc = 0
    for i, w in enumerate(s):
        if w == 'o' and i > lp + c:
            ls.add(i)
            lp = i
            lc += 1

    if lc > k:
        return []

    rp = n + c
    ans = []
    for i in range(n - 1, -1, -1):
        w = s[i]
        if w == 'o' and i < rp - c:
            if i in ls:
                ans.append(i + 1)
            rp = i

    ans.reverse()
    return ans


n, k, c = map(int, input().split())
s = input()
ans = solve(n, k, c, s)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:


n, k, c = [0] * 3
s = ""

def format_input(filename = None):
	global n, k, c
	global s
	if filename == None:
		n, k, c = list(map(int, input().split()))
		s = str(input())

	elif filename == '__random__':
		from random import randint as rng
		from random import choices
		n = rng(1, 2 * 10**5)
		k = rng(1, n)
		c = rng(0, n)
		s = ''.join(choices('ox', k = n))
		print(n, k, c)
		print(s)

def get_answer():
	left = []
	pointer = 0
	while pointer < n and len(left) < k:
		if s[pointer] == 'o':
			left.append(pointer + 1)
			pointer += c + 1
		else:
			pointer += 1

	right = []
	pointer = n - 1
	while pointer >= 0 and len(right) < k:
		if s[pointer] == 'o':
			right.append(pointer + 1)
			pointer -= c + 1
		else:
			pointer -= 1

	fixed = []
	if len(left) == k and len(right) == k:
		for i in range(k):
			if left[i] == right[-(i+1)]:
				fixed.append(left[i])

	for i in range(len(fixed)):
		print(fixed[i])

if __name__ == '__main__':
	format_input()

	get_answer()

Submission status: Accepted

Solution code:
#差がC以下はダメ（Cもダメ）
N,K,C=map(int,input().split())
S=input()
X=[]
for i in range(N):
    if S[i]=="o":
        X.append(i+1)
M=len(X)
#例外処理（M=1のとき）
if M==1:
    #このときK==1
    print(X[0])
    exit()

#X[i]日に働くとき、その直前or直後で働ける最も近い日のindex
L=[-1 for i in range(M)]
R=[-1 for i in range(M)]
j=1
for i in range(M-1):
    while(j<M):
        if X[j]-X[i]>=C+1:
            R[i]=j
            break
        else:
            j+=1
j=M-2
for i in range(M-1,0,-1):
    while(j>=0):
        if X[i]-X[j]>=C+1:
            L[i]=j
            break
        else:
            j-=1
LD=[-1 for i in range(M)]
RD=[-1 for i in range(M)]
def Ldfs(i):
    if LD[i]!=-1:
        return LD[i]
    if L[i]==-1:
        LD[i]=1
        return 1
    else:
        LD[i]=Ldfs(L[i])+1
        return Ldfs(L[i])+1
def Rdfs(i):
    if RD[i]!=-1:
        return RD[i]
    if R[i]==-1:
        RD[i]=1
        return 1
    else:
        RD[i]=Rdfs(R[i])+1
        return Rdfs(R[i])+1
for i in range(M):
    Ldfs(i)
    Rdfs(M-1-i)
Y=[0 for i in range(M)]
Y[0]=RD[1]
Y[-1]=LD[-2]
for i in range(1,M-1):
    Y[i]=LD[i-1]+RD[i+1]
for i in range(M):
    if Y[i]<K:
        print(X[i])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,c,k = LI()
    s = input()
    k += 1
    dpl = [0]*n
    if s[0] == "o":
        dpl[0] = 1
    else:
        dpl[0] = 0
    for i in range(1,n):
        dpl[i] = dpl[i-1]
        if s[i] == "o":
            dpl[i] = max(dpl[i-k]+1,dpl[i])
    dpr = [0]*n
    if s[-1] == "o":
        dpr[-1] = 1
    else:
        dpr[-1] = 0
    for i in range(n-1)[::-1]:
        dpr[i] = dpr[i+1]
        if s[i] == "o":
            dpr[i] = max(dpr[(i+k)%n]+1, dpr[i])
    dpl = [0]+dpl
    dpr += [0]
    ans = []
    for i in range(n):
        if dpl[i]+dpr[i+1] < c:
            print(i+1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, K, D = map(int, input().split())
S = [True if x == 'o' else False for x in input()]

l_lst, r_lst = [], []
i = 1
for _ in range(K):
    while not S[i - 1]:
        i += 1
    l_lst.append(i)
    i += D + 1

i = N
for _ in range(K):
    while not S[i - 1]:
        i -= 1
    r_lst.append(i)
    i -= D + 1
r_lst.reverse()

for i in range(K):
    ans = l_lst[i]
    if ans == r_lst[i]:
        print(ans)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = input()
frt = [0]*n
bck = [0]*n
cnt = 0
cntb = 0
prv = 0
prvb = 0
st = set()
stb = set()
for i in range(n):
  if cnt == 0 and s[i] == "o":
    cnt += 1
    frt[i] = 1
    prv = i
    st.add(i)
  elif i-prv > c and s[i] == "o":
    cnt += 1
    frt[i] = cnt
    prv = i
    st.add(i)
for i in range(n)[::-1]:
  if cntb == 0 and s[i] == "o":
    cntb += 1
    bck[i] = 1
    prvb = i
    stb.add(i)
  elif prvb-i > c and s[i] == "o":
    cntb += 1
    bck[i] = cntb
    prvb = i
    stb.add(i)
ans = []
for i in range(n):
  if i not in st or i not in stb:
    continue
  if frt[i]-1 + bck[i]-1 >= k:
    continue
  print(i+1)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K, C = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# dp1[i]: i 日目までに働ける日数
dp1 = [0] * (N + 1)
cnt = 0
rem = -1
for i, c in enumerate(S):
    if rem < 0 and c == 'o':
        cnt += 1
        rem = C
    dp1[i + 1] = cnt
    rem -= 1

# dp2[i]: i 日以降働ける日数
dp2 = [0] * (N + 1)
cnt = 0
rem = -1
for i, c in reversed(list(enumerate(S))):
    if rem < 0 and c == 'o':
        cnt += 1
        rem = C
    dp2[i] = cnt
    rem -= 1

# for a, b in zip(dp1[1:], S):
#     print(a, b)
# print()
# for a, b in zip(dp2[1:], S):
#     print(a, b)

for i, (c, cnt1, cnt2) in enumerate(zip(S, dp1, dp2[1:]), start=1):
    # print(i, c, cnt1, cnt2, cnt1 + cnt2)
    if cnt1 + cnt2 < K:
        print(i)

Submission status: Accepted

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]:
    if s[i] == 'x':
        dp[i] = dp[i+1]
        continue
    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: Accepted

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


# 前からDP
start = S.index("o")
dp1 = [-1] * N
dp1[start] = 1
i = start
while dp1[i] < K:
    tmp = dp1[i]

    i += C
    while i < N:
        i += 1
        if S[i] == "o":
            dp1[i] = tmp + 1
            break

# 後ろからDP
T = S[::-1]
start = T.index("o")
dp2 = [-1] * N
dp2[start] = K
i = start
while dp2[i] > 1:
    tmp = dp2[i]
    i += C
    while i < N:
        i += 1
        if T[i] == "o":
            dp2[i] = tmp - 1
            break
dp2.reverse()

ans = []
for i in range(N):
    if dp1[i] == -1 or dp2[i] == -1:
        continue
    if dp1[i] == dp2[i]:
        ans.append(i + 1)

if ans:
    print(*ans, sep="\n")

Submission status: Accepted

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


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

if c == 0:
    res = []
    for i in range(n):
        if s[i] == "o":
            res.append(i+1)
    if len(res) <= k:
        for e in res:
            print(e)
    exit()


back = [0]*(n+1)
fro = [0]*(n+1)

for i in range(n-1,-1,-1):
    if i >= n-c:
        if back[i+1] == 1:
            back[i] = 1
        elif s[i] == "o":
            back[i] = 1
        else:
            back[i] = 0
    else:
        if s[i] == "o":
            back[i] = max(back[i+c+1]+1,back[i+1])
        else:
            back[i] = back[i+1]

for i in range(n):
    if i <= c:
        if fro[i-1] == 1 or s[i] == "o":
            fro[i] = 1
        else:
            fro[i] = 0

    else:
        if s[i] == "o":
            fro[i] = max(fro[i-c-1]+1,fro[i-1])
        else:
            fro[i] = fro[i-1]


for i in range(n):
    if i == 0:
        if n == 1:
            print(1)
        else:
            if back[1] < k:
                print(1)
        continue

    if back[i+1] + fro[i-1] < k:
        print(i+1)

Submission status: Accepted

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())
    X.sort()
    ans = []
    prev = 10**9
    for i in range(K-1, -1, -1):
        x = X[i]
        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: Accepted

Solution code:
N,K,C = map(int,input().split())
S = list(input())
L = [(0,-C) for i in range(N+1)]
R = [(0,N+C+1) for i in range(N+1)]
for i in range(N):
	l = L[i]
	s = S[i]
	if s == "o" and l[1] + C < i+1:
		L[i+1] = (l[0]+1, i+1)
	else:
		L[i+1] = L[i]

	r = R[N-i]
	s = S[N-1-i]
	if s == "o" and N-i + C < r[1]:
		R[N-i-1] = (r[0]+1, N-i)
	else:
		R[N-i-1] = R[N-i]

R = [(0,0)] + R

for n in range(N):
	d = n+1
	if d == 1:
		if R[2][0] < K:
			print(d)
		continue
	if d == N:
		if L[N-1][0] < K:
			print(d)
		continue
	l = L[d-1]
	r = R[d+1]
	w_l, w_r=0, 0
	if l[1] + C > N:
		w_l = l[0]
	else:
		w_l = l[0] + R[max(d+1, l[1]+C)][0]
	if r[1] - C <= 0:
		w_r = r[0]
	else:
		w_r = r[0] + L[min(d-1, r[1]-C)][0]
	if w_l < K and w_r < K:
		print(d)

Submission status: Accepted

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

if c == 0:
    o = s.count('o')
    if o == k:
        for i in range(n):
            if s[i] == 'o':
                print(i + 1)
    exit()

pr = [0] * n
for i in range(n):
    if s[i] == 'o':
        pr[i] = 1
for i in range(n):
    if i >= 1:
        pr[i] = max(pr[i - 1], pr[i])
    if s[i] == 'o' and i >= c + 1:
        pr[i] = max(pr[i], pr[i - (c + 1)] + 1)
sf = [0] * n
for i in range(n):
    if s[i] == 'o':
        sf[i] = 1
for i in range(n - 1, -1, -1):
    if i + 1 < n:
        sf[i] = max(sf[i + 1], sf[i])
    if s[i] == 'o' and i + (c + 1) < n:
        sf[i] = max(sf[i], sf[i + (c + 1)] + 1)

b = [0] * (n + 1)
for i in range(n + c + 1):
    j = i - (c + 1)
    u = sf[i] if 0 <= i < n else 0
    v = pr[j] if 0 <= j < n else 0
    if u + v < k:
        b[min(max(0, i), n)] -= 1
        b[max(0, min(n, j + 1))] += 1

cb = 0
for i in range(n):
    cb += b[i]
    if cb >= c and s[i] == 'o':
        print(i + 1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k, c = map(int, readline().split())
s = input()
cnt_1 = 0
cnt_2 = n - 1
cnt = [0, 0]
ans = [0] * n
for i in range(n):
    if s[cnt_1] == 'o':
        ans[cnt_1] += 1
        cnt_1 += c
        cnt[0] += 1
    cnt_1 += 1
    if cnt_1 > n - 1:
        break
for i in range(n):
    if s[cnt_2] == 'o':
        ans[cnt_2] += 1
        cnt_2 -= c
        cnt[1] += 1
    cnt_2 -= 1
    if cnt_2 < 0:
        break
if max(cnt) > k:
    print()
else:
    for i in range(n):
        if ans[i] == 2:
            print(i + 1)

Submission status: Accepted

Solution code:
def solve(n, k, c, s):
    # greedy from first
    g_f = [0] * n
    last_worked = - c - 1
    cnt = 0
    for i in range(n):
        if last_worked + c + 1 <= i and s[i] == "o":
            cnt += 1
            g_f[i] = cnt
            last_worked = i
        if cnt == k:
            break
    # print(g_f)

    # greedy from last
    g_l = [0] * n
    last_worked = n + c
    cnt = k
    for i in range(n - 1, -1, -1):
        if i + c + 1 <= last_worked and s[i] == "o":
            g_l[i] = cnt
            cnt -= 1
            last_worked = i
        if cnt == 0:
            break
    # print(g_l)

    res = []
    for i in range(n):
        if 0 < g_f[i] == g_l[i]:
            res.append(i + 1)
    return res


def main():
    n, k, c = map(int, input().split())
    s = input()
    res = solve(n, k, c, s)
    for r in res:
        print(r)


def test():
    assert solve(11, 3, 2, "ooxxxoxxxoo") == [6]
    assert solve(5, 2, 3, "ooxoo") == [1, 5]
    assert solve(5, 1, 0, "ooooo") == []
    assert solve(16, 4, 3, "ooxxoxoxxxoxoxxo") == [11, 16]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

max_ = 0
dp = [0] * (n + 1)
cnt = {0: 0}
for i in range(n)[::-1]:
    max_ = max(dp[min(i + c + 1, n)] + 1, max_)
    if s[i] == "o":
        dp[i] = max_
        if dp[i] not in cnt:
            cnt[dp[i]] = 1
        else:
            cnt[dp[i]] += 1

if max_ > k:
    exit()
  
i = 0
ans = []
while True:
    if i >= n:
        break
        
    if s[i] == "x":
        i += 1
        continue
        
    if k == dp[i]:
        if cnt[k] == 1:
            ans.append(i)
        for j in range(c + 1):
            cnt[dp[min(i + j, n)]] -= 1
        i = i + c + 1
        k -= 1
        continue
    else:
        cnt[dp[i]] -= 1
        i += 1
for i in ans:
    print(i + 1)

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = input()
def solve():
    if C==0:
        a = [i+1 for i,c in enumerate(S) if c=='o']
        if len(a)==K:
            print(*a, sep='\n')
        else:
            print()
        exit()
    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: Accepted

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

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

O = 'o'
X = 'x'


l2r = [None] * N

offset = 0
count = 0
while True:
    i = offset
    while i < N:
        if S[i] == O:
            offset = i + C + 1
            l2r[i] = 1
            count += 1
            break
        i += 1

    if i >= N:
        break

if count > K:
    exit(0)

r2l = [None] * N
count = 0
offset = N - 1
while True:
    i = offset
    while i > -1:
        if S[i] == O:
            offset = i - C - 1
            r2l[i] = 1
            count += 1
            break
        i -= 1
    if i <= -1:
        break


for i in range(N):
    if l2r[i] == 1 and r2l[i] == 1:
        print(i + 1)