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:
import sys
n, k, c = [int(x) for x in input().split()]
s = input()
counts = [[0] * 2 for i in range(n)]
for i in range(n):
    if s[i] == 'x':
        if i > 0:
            counts[i] = [max(counts[i - 1]), 0]
        else:
            counts[0]= [0, 0]
        continue
    if i == 0:
        counts[0]= [0, 1]
    elif i <= c:
        counts[i] = [max(counts[i - 1]), 1]
    else:
        counts[i] = [max(counts[i - 1]), max(counts[i - c - 1]) + 1]
r = []
checkk = k
nextgap = n
for i in range(n - 1, -1, -1):
    if i < nextgap and counts[i][1] >= checkk:
        if counts[i][0] < checkk:
            r.append(i + 1)
        checkk -= 1
        if checkk == 0:
            break
        nextgap = i - c
for i in range(len(r) - 1, -1, -1):
    print(r[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K,C=map(int,input().split())
    S=list(map(int,input().replace('o','1').replace('x','0')))
    T=[0]*(N+1)
    l0=[]
    l1=[]
    r0=-INF
    r1=-INF
    for i in range(N):
        if len(l0)<K and i>r0 and S[i]==1:
            l0.append(i)
            r0=i+C
        if len(l1)<K and i>r1 and S[N-1-i]==1:
            l1.append(N-1-i)
            r1=i+C
    l1.reverse()
    ans=[]
    for i in range(K):
        if l0[i]==l1[i]:
            ans.append(l0[i])
    ans.sort()
    for x in ans:
        print(x+1)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = list(input())
os = 0
for ss in s:
    if ss == 'o':
        os += 1
s2 = list(reversed(s))

if c == 0 and os > k:
    exit(0)

def calc(s):
    global n, k, c
    answer = set()
    pre = None
    for idx, i in enumerate(s):
        if i == 'o' and (pre is None or idx > pre + c):
            answer.add(idx + 1)
            # 前回働いた日を記録
            pre = idx
        if len(answer) >= k:
            return answer

answer1 = calc(s)
answer2 = calc(s2)
answer2 = set(map(lambda x: len(s2) - x + 1, answer2))

for i in sorted(list(answer1 & answer2)):
    print(i)

Submission status: Accepted

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

ANS = [0] * n
A = [0] * n
B = []
NX = [10**8] * n
kk = k
for i in range(n):
    if kk == 0:
        break
    if s[i] == "o" and (len(B) == 0 or i > B[-1]+c):
        A[i] = 1
        ANS[i] = 1
        B.append(i)
        kk -= 1

nx = 10**8
for i in range(n-1,-1,-1):
    if A[i] == 1:
        nx = i
    NX[i] = nx

# print(B)
# print(NX)

bf = 10**8
nx = 10**8
for i in range(n-1,-1,-1):
    # print(i, NX[i],nx)
    if A[i] == 1:
        nx = i
    if s[i] == "o" and A[i] == 0 and nx-i > c:
        # print("ok",i)
        nx = i
        bf = min(bf, i) - 1
        # print("bf s",bf)
        while bf >= 0 and A[bf] == 0:
            bf -= 1
        # print("bf",bf)
        if bf >= 0:
            A[bf] = 0
            ANS[bf] = 0
            A[i] = 1
        # print(A)

# print(ANS)
for i in range(len(ANS)):
    if ANS[i] == 1:
        print(i+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

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

dp1 = [0] * (n+1)
dp2 = [0] * (n+1)
# dp[i] = (選択したなかで一番左側のindex,選択した個数)
now = 10 ** 7;count = 0
for i in range(n-1,-1,-1):
  if s[i] == "o" and i + c < now:
    count += 1; now = i
    dp1[i] = (i,count)
  elif i == n-1:dp1[i] = (inf,0)
  else:
    dp1[i] = dp1[i+1]

now = - 10 ** 7;count = 0
for i in range(n):
  if s[i] == "o" and now + c < i:
    count += 1; now = i
    dp2[i] = (i,count)
  elif i == 0:dp2[i] = (-inf,0)
  else:
    dp2[i] = dp2[i-1]

# dp1:右から　　dp2:左から
if dp1[1][1] < k:print(1)
for i in range(1,n-1):
  index0,count0 = dp1[i+1]
  if index0 - c >= 0:
    count0 += dp2[min(index0-c,i-1)][1]
  if count0 < k:
    print(i+1)
if dp2[n-2][1] < k:print(n)
# print(dp2)

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = [c == "o" for c in input().strip()]

prev = -C - 1
count = 0
work_l = []
for i, c in enumerate(S):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_l.append(i)

prev = -C - 1
count = 0
work_r = []
for i, c in enumerate(reversed(S)):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_r.append(N - 1 - i)

work_r.reverse()

if len(work_l) == K and len(work_l) == len(work_r):
	for l, r in zip(work_l, work_r):
		if l == r:
			print(l + 1)

Submission status: Accepted

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

l = [0 for _ in range(n + 1)]
prev = -c
for i in range(1, n + 1):
    l[i] = l[i - 1]
    if prev + c < i and s[i - 1] == 'o':
        l[i] += 1
        prev = i
r = [0 for _ in range(n + 1)]
prev = n + c
for i in range(n - 1, -1, -1):
    r[i] = r[i + 1]
    if i < prev - c and s[i] == 'o':
        r[i] += 1
        prev = i
cnt = [1 if c == 'o' else 0 for c in s]
for i in range(n):
    if 0 < i - c:
        cnt[i] += l[i - c]
    if i + c + 1 < n + 1:
        cnt[i] += r[i + c + 1]
ans = [s[i] == 'o' and cnt[i] == k for i in range(n)]
prev = -c - 1
for i in range(n):
    if s[i] == 'o' and cnt[i] == k:
        if i <= prev + c:
            ans[i] = False
        prev = i
prev = n + c + 1
for i in range(n - 1, -1, -1):
    if s[i] == 'o' and cnt[i] == k:
        if prev - c <= i:
            ans[i] = False
        prev = i
for i in range(n):
    if ans[i]:
        print(i + 1)

Submission status: Accepted

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

HAYAI = []
OSOI = []

now = 0
c = 0
while now < N and c<K:
    if S[now]=='o':
        HAYAI.append(now)
        now += C+1
        c += 1
    else:
        now += 1
        
SS = S[::-1]
now = 0
c = 0
while now < N and c<K:
    if SS[now]=='o':
        OSOI.append(N-now-1)
        now += C+1
        c += 1
    else:
        now += 1
#print(HAYAI)
OSOI = OSOI[::-1]
#print(OSOI)
for i in range(K):
  if HAYAI[i]==OSOI[i]:
    print(HAYAI[i]+1)

Submission status: Accepted

Solution code:
def get_max(ar, c):
    cnt = 0
    rtn = []
    rest = 0
    for a in ar:
        if a == "o" and rest <= 0:
            cnt += 1
            rest = c
        else:
            rest -= 1
        rtn.append(cnt)
    return rtn


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

from_start = get_max(s, c)
from_last = get_max(s[::-1], c)[::-1]
for i in range(n):
    aa = 0 if i == 0 else from_start[i - 1]
    aaa = from_start[i]
    bb = 0 if i == n - 1 else from_last[i + 1]
    bbb = from_last[i]
    if aaa == aa + 1 and bbb == bb + 1 and aaa + bb == k:
        print(i + 1)

Submission status: Accepted

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

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

c = 0
p = -1
for i in range(N):
  if S[i]=="o":
    if c+(T1[i+1] if i+1<N else 0)<K:
      print i+1
    if p==-1 or p+C<i:
      c += 1
      p = i

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k,c=map(int,input().split())
s=input().rstrip()
nc=[0]*n
co=0
d=c+1
for i in range(n):
    if s[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[i]+=1
        else:
            d+=1
    if co==k:
        break
sn=list(s)
sn.reverse()
co=0
d=c+1
for i in range(n):
    if sn[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[n-1-i]+=1
        else:
            d+=1
    if co==k:
        break
co=0
da=c+1
db=c+1
for i in range(n):
    if s[i]=='x':
        da+=1
    else:
        if da>=c:
            da=0
            co+=1
            nc[i]+=1
        else:
            da+=1
    if co==k:
        break
    if sn[i]=='x':
        db+=1
    else:
        if db>=c:
            db=0
            co+=1
            nc[n-1-i]+=1
        else:
            db+=1
    if co==k:
        break
for i in range(n):
    if nc[i]==3:
        print(i+1)

Submission status: Accepted

Solution code:
class SegmentTree:
    """Segment Tree (Point Update & Range Query)
    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)
    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N - 1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )

    def __getitem__(self, k):
        return self.segtree[self.N - 1 + k]

    def query(self, low, high):
        # query [l, r)
        low, high = low + self.N, high + self.N
        left_ret, right_ret = self.default, self.default
        while low < high:
            if low & 1:
                left_ret = self.f(left_ret, self.segtree[low - 1])
                low += 1
            if high & 1:
                high -= 1
                right_ret = self.f(self.segtree[high - 1], right_ret)
            low, high = low >> 1, high >> 1
        return self.f(left_ret, right_ret)


def main() -> None:
    N, K, C = map(int, input().split())
    S = [1 if s == "o" else 0 for s in input()]
    left, right = [-1] * N, [-1] * N
    max_v = -1
    for i in range(N):
        if i - C - 1 >= 0:
            max_v = max(max_v, left[i - C - 1])
        if S[i] == 1:
            left[i] = max_v + 1
    max_v = -1
    for i in reversed(range(N)):
        if i + C + 1 <= N - 1:
            max_v = max(max_v, right[i + C + 1])
        if S[i] == 1:
            right[i] = max_v + 1
    work_day = [max(0, left[i] + right[i] + 1) for i in range(N)]
    #print(work_day)
    if max(work_day) > K:
        return
    segt = SegmentTree.create_from_array(work_day, max, 0)
    ans = []
    for i in range(N):
        if work_day[i] < K:
            continue
        m = max(segt.query(max(0, i - C), i), segt.query(i+1, min(i + 1 + C, N)))
        if m >= K:
            continue
        # m = max(segt.query(0, max(0, i - C)), segt.query(min(N, i + 1 + C), N))
        # if m >= K + 1:
        #     continue
        ans.append(i + 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp1 = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp1[i] = max(dp1[j] + 1, dp1[i + 1])
    else:
        dp1[i] = max(dp1[j], dp1[i + 1])

dp2 = [0] * (n + 1)
for i in range(n):
    j = max(i - c - 1, -1)
    if s[i] == 'o':
        dp2[i] = max(dp2[j] + 1, dp2[i - 1])
    else:
        dp2[i] = max(dp2[j], dp2[i - 1])

# print(dp1)
# print(dp2)


def check(idx):
    if s[idx] == 'x':
        return False

    if dp1[idx + 1] + dp2[idx - 1] >= k:
        return False
    else:
        return True


for i in range(n):
    if check(i):
        print(i + 1)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

n,k,c = map(int, input().split())
S = [True if i=='o' else False for i in input()]

if n == c:
    ANS = []
    if sum(S) == 1:
        for i in range(n):
            if S[i]:
                ANS.append(i+1)
    print(*ANS, sep='\n')
    exit()



left = [0]*n
right = [0]*n
c = c+1
if S[0]:
    left[0] = 1

for i in range(1, c):
    if S[i]:
        left[i] = 1
    left[i] = max(left[i], left[i-1])

for i in range(c, n):
    if S[i]:
        left[i] = left[i-c] + 1
    else:
        left[i] = left[i-1]
if S[-1]:
    right[-1] = 1
for i in range(n-c, n-1)[::-1]:
    if S[i]:
        right[i] = 1
    right[i] = max(right[i], right[i+1])
for i in range(n-c)[::-1]:
    if S[i]:
        right[i] = right[i+c] + 1
    else:
        right[i] = right[i+1]

ans = []
for i in range(n):
    if S[i]:
        tl = 0
        tr = 0
        if i>0:
            tl = left[i-1]
        if i<n-1:
            tr = right[i+1]
        if tl + tr < k:
            ans.append(i+1)

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

Submission status: Accepted

Solution code:
import bisect

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

ans = []
last_set = last_set[::-1]
indices = indices[::-1]
pre = -1000000
for day in last_set:
  i = bisect.bisect_left(indices, day)
  if i == 0:
    ans.append(day)
    pre = day
  else:
    ii = indices[i-1]
    if abs(ii - pre) <= C:
      ans.append(day)
      pre = day
    else:
      iii = bisect.bisect_left(indices, pre+C+1)
      if iii < N:
        pre = min(indices[iii], ii)
      else:
        pre = ii

for day in ans:
  print(day)

Submission status: Accepted

Solution code:
import sys

inf = float('inf')
n, k, c = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

def main():
    dp_l = [[0] * 2 for _ in range(n + 2)]
    for i in range(n):
        dp_l[i+1][0] = max(dp_l[i][0], dp_l[i][1])
        if s[i] == 'o':
            if i + 1 - c < 0:
                dp_l[i+1][1] = 1 
            else:
                dp_l[i+1][1] = dp_l[i+1-c][0] + 1
    dp_r = [[0] * 2 for _ in range(n + 2)]
    for i in range(n, 0, -1):
        dp_r[i][0] = max(dp_r[i+1][0], dp_r[i+1][1])
        if s[i-1] == 'o':
            if i + c > n + 1:
                dp_r[i][1] = 1
            else:
                dp_r[i][1] = dp_r[i+c][0] + 1

    for i in range(1, n + 1):
        if s[i-1] == 'o':
            if dp_l[i][0] + dp_r[i][0] < k:
                print(i)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

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


def solve_shortest(s):

    sche = []
    t = 0
    day = 0
    for i,ch in enumerate(s):
        if (ch=="o") & (i>=t):
            sche += [i]
            t = i+c+1
            day += 1
        if day == k: break
    else:
        return
    
    return sche

sche1 = solve_shortest(s)
sche2 = solve_shortest(s[::-1])

ans = []
for x,y in zip(sche1,sche2[::-1]):
    if x+y == n-1:
        ans.append(x+1)
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
S=list(input())
A=[]
B=[]
i=0
while i<n:
  if S[i]=="o":
    A.append(i)
    i=i+c+1
  else:
    i=i+1
i=n-1
while i>-1:
  if S[i]=="o":
    B.append(i)
    i=i-c-1
  else:
    i=i-1
if len(A)>k or len(B)>k:
  exit()
B.sort()
for i in range(k):
  if A[i]==B[i]:
    print(A[i]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K,C=map(int,input().split())
    S=list(map(int,input().replace('o','1').replace('x','0')))
    T=[0]*(N+1)
    for i in range(N):
        T[i+1]=T[i]+S[i]
    l0=[]
    l1=[]
    r0=-INF
    r1=-INF
    for i in range(N):
        if len(l0)<K and i>r0 and S[i]==1:
            l0.append(i)
            r0=i+C
        if len(l1)<K and i>r1 and S[N-1-i]==1:
            l1.append(N-1-i)
            r1=i+C
    l1.reverse()
    ans=[]
    for i in range(K):
        if l0[i]==l1[i]:
            if i==0 or i==K-1:
                ans.append(l0[i])
            else:
                q=T[l1[i+1]-C]-T[l0[i-1]+C+1]
                if l0[i-1]+C+1<l1[i+1]-C and q<2:
                    ans.append(l0[i])
    ans.sort()
    for x in ans:
        print(x+1)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k,c = map(int, input().split())
s = input()
ok = []
for i,x in enumerate(s):
    if x == "o":
        ok.append(i)

fast = []
pre = -10**10
for i,x in enumerate(s):
    if x == "o" and pre + c < i:
        fast.append(i+1)
        pre = i
    if len(fast) == k:
        break
late = []
pre = -10**10
for i,x in enumerate(s[::-1]):
    if x == "o" and pre + c < i:
        late.append(n-i)
        pre = i
    if len(late) == k:
        break
late = late[::-1]
for i in range(k):
    if fast[i] == late[i]:
        print(fast[i])

Submission status: Accepted

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

W = [0] * N

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

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

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

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

BDP = [0] + BDP

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

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

if BDP[-1] < K:
  exit()

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

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

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

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

Submission status: Accepted

Solution code:
#E
inf = float("inf")
N,K,C = map(int,input().split())
S = list(str(input()))

old = -inf
used = [-1 for _ in range(N)] #if used then used[i] = 1
count = 0
for i in range(N):
    if S[i] == "o":
        if i > old+C and count < K:
            old = i
            used[i] = 1
            count+=1
        else:
            used[i] = 0
            
ans = []
front = N-1
#print(used)
hatu = True
for i in range(N):
    I = N-(i+1)
    if used[I] == 1:
        #print(I,front)
        flag = True
        if hatu:
            hatu = False
            rest = front-I
            for j in range(rest):
                if used[front-j-1] != -1:
                    front -= j+1
                    flag = False
                    break
        else:
            rest = front-I
            for j in range(rest):
                #print(I,front-j-1)
                if used[front-j-1] != -1 and front-j-1+C < front:
                    front -= j+1
                    if front != I:
                        flag = False
                    break
        
        if flag:
            ans.append(I+1)
            front = I
        #print(front)
            
    
ans.sort()                
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n, kk, c = [int(i) for i in input().split()]
c = c+1
s = input()
dp1 = []
j = -c
k = 0
for i in range(n):
    if s[i] != "x" and j + c <= i:
        k += 1
        j = i
    dp1.append([k, j])

dp2 = []
j = n-1+c
k = 0
for i in reversed(range(n)):
    if s[i] != "x" and j - c >= i:
        k += 1
        j = i
    dp2.append([k, j])
dp2.reverse()


for i in range(n):
    if s[i] == "x":
        continue
    a, b = dp1[i - 1] if i > 0 else[0, -c]
    b += c
    b = max(b, i+1)
    if b == i:
        b += 1
    if b < n:
        a += dp2[b][0]
    if a < kk:
        print(i+1)

Submission status: Accepted

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

chuncks = []
last_workday = -c-10
for i in range(n):
	if s[i] == 'o':
		if len(chuncks) > 0 and i - chuncks[-1][0] <= c:  # in one chunck 
			chuncks[-1].append(i)
		else:
			chuncks.append([i])
		last_workday = i

# print("chuncks before", chuncks)

l = len(chuncks)
for i in range(l):
	if i != 0:
		# check with previous
		to_start = 0
		for j in range(len(chuncks[i])):
			if chuncks[i][j] <= chuncks[i-1][0] + c:
				to_start = j+1
		chuncks[i] = chuncks[i][to_start:]

for i in range(l-1, -1, -1):
	if i != l-1:
		# check with the next one
		to_finish = len(chuncks[i]) # not inclusive
		for j in range(len(chuncks[i])-1, -1, -1):
			if chuncks[i][j] + c >= chuncks[i+1][-1]:
				to_finish = j
		chuncks[i] = chuncks[i][:to_finish]

# print("chuncks after", chuncks)

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

if l > k:
	pass
else:
	for i in range(len(chuncks)):
		if len(chuncks[i]) == 1:
			print(chuncks[i][0]+1)

# print("chuncks after", chuncks)

Submission status: Accepted

Solution code:
n,k,c=map(int, input().split())
s = input()
leftmost = []
cursor = 0
for _ in range(k):
    while s[cursor] == 'x':
        cursor += 1
    leftmost.append(cursor)
    cursor += c+1
rightmost = []
cursor = n-1
for _ in range(k):
    while s[cursor] == 'x':
        cursor -= 1
    rightmost.append(cursor)
    cursor -= c+1
rightmost.reverse()
for l, r in zip(leftmost, rightmost):
    if l == r:
        print(l+1)
#print(leftmost, rightmost)

Submission status: Accepted

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

left = [None] * N
right = [None] * N

cnt = 0
penalty = 0
for idx in range(N):
    if S[idx] == 'o' and penalty == 0:
        left[idx] = cnt
        cnt += 1
        penalty = C + 1
    #
    if cnt >= K: continue
    penalty = max(0, penalty - 1)

cnt = 0
penalty = 0
for idx_inv in range(N):
    idx = N - 1 - idx_inv
    if S[idx] == 'o' and penalty == 0:
        right[idx] = K - 1 - cnt
        cnt += 1
        penalty = C + 1
    #
    if cnt >= K: continue
    penalty = max(0, penalty - 1)



# print("#", left, right)
for idx in range(N):
    if left[idx] != None and right[idx] != None and left[idx] == right[idx]:
        print(idx + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,k,c = l_in()
S = s_in()


i = 0
left = set()

while i < n:
    if S[i] == 'o':
        left.add(i)
        i += 1+c
    else:
        i += 1

i = n-1
right = set()

while i >= 0:
    if S[i] == 'o':
        right.add(i)
        i -= 1+c
    else:
        i -= 1

if len(left) == k and len(right) == k:
    for i in sorted(list(left.intersection(right))):
        print(i+1)

Submission status: Accepted

Solution code:
N,K,C = map(int,input().split())
S = input()
dp1 = [0]*N
dp2 = [0]*N

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

c = 0
if S[-1]=='o':
    dp2[-1] = 1
    c = C
for i in range(N-2,-1,-1):
    if c==0 and S[i]=='o':
        dp2[i] = dp2[i+1]+1
        c = C
    else:
        c = max(0,c-1)
        dp2[i] = dp2[i+1]

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
n, k, c = map(int, input().split())
s = input()
front = [0 for _ in range(n)]
back = [0 for _ in range(n)]

rm = -10**6
cur = 0
for i in range(n):
	if s[i] == "o" and i - rm > c:
		cur += 1
		front[i] = cur
		rm = i

if cur > k:
	sys.exit()

lm = 10**6
cur = k+1
for i in range(n-1, -1, -1):
	if s[i] == "o" and lm - i > c:
		cur -= 1
		back[i] = cur
		lm = i

for i in range(n):
	if front[i] > 0 and front[i] == back[i]:
		print(i+1)

Submission status: Accepted

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def construct(self, a):
        for i, x in enumerate(a):
            self.data[i+self.n0-1] = x
        for i in range(self.n0-2, -1, -1):
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])


n,k,c = map(int, input().split())
s = input()
f = [1]*n
for i in range(n):
    if s[i] == "x":
        f[i] = 0

foward = RangeMinimumQuery(n, max, 0)
for i in range(n):
    if f[i]:
        j = i-(c+1)
        s = foward.query(0,j+1)
        foward.update(i, s+1)

backward = RangeMinimumQuery(n, max, 0)
for i in reversed(range(n)):
    if f[i]:
        j = i+(c+1)
        s = backward.query(j,n)
        backward.update(i, s+1)

first = [-1]*(n+10)

ans = []
for i in range(n):
    if f[i] == 0:
        continue
    left = foward.query(0, i)
    if left == 0:
        l = i+1
    else:
        l = max(i+1, first[left]+c+1)
    if l >= n:
        right = 0
    else:
        right = backward.query(l,n)
    if left + right < k:
        ans.append(i+1)
    cur = foward.query(i,i+1)

    if first[cur] == -1:
        first[cur] = i

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

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()
l=[None]*N
c=0
t=0
while c<K:
    if S[t]=="o":
        l[t]=c
        c+=1
        t+=C+1
    else:
        t+=1
t=N-1
a=[]
while c:
    if S[t]=="o":
        c-=1
        if c==l[t]:
            a.append(t+1)
        t-=C+1
    else:
        t-=1
print(*a[::-1],sep="\n")

Submission status: Accepted

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

ans = [0] * n

p = 0
lasto = - c - 1

for i in range(n):
    if p == k:
        break
    if s[i] == "o":
        if i > lasto + c:
            ans[i] += 1
            p += 1
            lasto = i

s = s[::-1]
p = 0
lasto = - c - 1

q = 0

for i in range(n):
    if s[i] == "o":
        if i > lasto + c:
            ans[n - 1 - i] += 1
            p += 1
            lasto = i
            if p > k:
                q = 1
                break

if q == 0:
    for i in range(n):
        if ans[i] == 2:
            print(i + 1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
i = 0
l = [0] * (n + 1)
r = [0] * (n + 1)
while i < n:
    if s[i] == 'o':
        l[i + 1] = 1
        i += c
    i += 1
i = n - 1
while i >= 0:
    if s[i] == 'o':
        r[i] = 1
        i -= c
    i -= 1
for i in range(n):
    l[i + 1] += l[i]
    r[n - i - 1] += r[n - i]
for i in range(n):
    if l[i] + r[i + 1] < k:
        print(i + 1)

Submission status: Accepted

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

left = [0] * (n+1)
right = [0] * (n+1)

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

for i in reversed(range(n)):
    if s[i] == 'o':
        if i + 1 + c < n:
            right[i] = max(right[i+1], right[i+1+c] + 1)
        else:
            right[i] = 1
    else:
        right[i] = right[i+1]

l = 0
r = 0

end = False
ans = []
for i in range(n):
    if left[l] > 0:
        r = max(r, l+c, i+1)
    else:
        r = max(r, i+1)
    r = min(r, n)
    while r <= n and left[l] + right[r] < k and l <= i:
        l += 1
        r = max(r, l+c-1)
    if l > i:
        ans.append(i+1)
    if r > n:
        if left[i] < k:
            ans.append(i+1)

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
c += 1
a = input()
b = a[::-1]
form = [0]
lat = [0]
for i in range(n):
  if a[i] == 'x':
    form.append(form[-1])
  else:
    try:
      form.append(max(form[-c]+1,form[-1]))
    except:
      form.append(1)
  if b[i] == 'x':
    lat.append(lat[-1])
  else:
    try:
      lat.append(max(lat[-c]+1,lat[-1]))
    except:
      lat.append(1)
form.append(form[-1])
lat.append(lat[-1])
lat.reverse()
#print(form)
#print(lat)
#print(len(form))
for i in range(n):
  if form[i] + lat[i+2] == k-1:
    print(i+1)