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:
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
    ans.sort()
    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: Accepted

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

N,K,C=map(int,input().split())
S="x"+input().strip()+"x"

N=len(S)
SUML=[0]*N
SUMR=[0]*N

NEXT=0
for i in range(N):
    if i>=NEXT and S[i]=="o":
        SUML[i]=SUML[i-1]+1
        NEXT=i+C+1
    else:
        SUML[i]=SUML[i-1]

S2=S[::-1]

NEXT=0
for i in range(N):
    if i>=NEXT and S2[i]=="o":
        SUMR[i]=SUMR[i-1]+1
        NEXT=i+C+1
    else:
        SUMR[i]=SUMR[i-1]

SUMR=SUMR[::-1]

ANS=[]
for i in range(1,N-1):
    if S[i]=="o" and SUML[i-1]+SUMR[i+1]==K-1:
        ANS.append(i)

print(*sorted(ANS))

Submission status: Accepted

Solution code:

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

S = input()

l = [0]

last = float("-inf")
for i in range(N):

    if i > last+C and S[i] == "o":
        l.append(l[-1]+1)
        last = i
    else:
        l.append(l[-1])

l.append(l[-1])

r = [0]
last = float("-inf")
for i in range(N):

    if i > last+C and S[N-1-i] == "o":
        r.append(r[-1]+1)
        last = i
    else:
        r.append(r[-1])

r.append(r[-1])
r.reverse()

for i in range(1,N+1):

    if S[i-1] == "o" and l[i-1] + r[i+1] < K:
        print (i)

Submission status: Accepted

Solution code:
n,k,c=map(int,input().split())
s=[i for i in input()]
a=[0 for i in range(n)]
b=[0 for i in range(n)]
i=0
while i<n:
    if s[i]=="o":
        a[i]=1
        i+=c
    i+=1
s.reverse()
i=0
while i<n:
    if s[i]=="o":
        b[i]=1
        i+=c
    i+=1
b.reverse()
if sum(a)>k:
    quit()
for i in range(n):
    if a[i] and b[i]:
        print(i+1)

Submission status: Accepted

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

INF = 1 << 20
ldp = [-INF] * n
rdp = [-INF] * n

past_max = 0

for i in range(n):
    if i-c-1>= 0: past_max = max(past_max, ldp[i-c-1])
    if s[i] == 'x': continue
    ldp[i] = past_max + 1

future_max = 0
for i in range(n-1, -1, -1):
    if i+c+1 < n: future_max = max(future_max, rdp[i+c+1])
    if s[i] == 'x': continue
    rdp[i] = future_max + 1

dist = [[] for i in range(k + 10)]

for i in range(n):
    if s[i] == 'x':continue
    if ldp[i] + rdp[i] - 1 != k:continue
    dist[ldp[i]].append(i)

for i in range(k+10):
    if len(dist[i]) == 1:
        print(dist[i][0] + 1)

Submission status: Accepted

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 + 1)
    for i in range(n):
        if s[i] == "o" and tmp + c + 1 <= i:
            tmp = i
            t_ans[i+1] = t_ans[i] + 1
        else:
            t_ans[i+1] = t_ans[i]
    tt = []
    tmp = 0
    for tmp, ai in enumerate(ans):
        if ai == 0:
            tt.append(str(ai + 1))
            continue
        if t_ans[ai] == tmp:
            tt.append(str(ai + 1))
    print("\n".join(tt))




    return


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

Submission status: Accepted

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

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

A = [0]
go = C
for s in S:
    if go >= C:
        if s == "o":
            A.append(A[-1]+1)
            go = 0
        else:
            A.append(A[-1])
    else:
        go += 1
        A.append(A[-1])

B = [0]*(N+1)
go = C
for i in reversed(range(N)):
    s = S[i]
    if go >= C:
        if s == "o":
            B[i] = B[i+1]+1
            go = 0
        else:
            B[i] = B[i+1]
    else:
        go += 1
        B[i] = B[i+1]

ans = []
for n in range(N):
    if S[n] == "o" and A[n] + B[n+1] < K:
        ans.append(str(n+1))

print("\n".join(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def compute(S):
    dp = [0] * N
    for i, x in enumerate(S):
        if i <= C:
            dp[i] = 1
        else:
            if x == 'x':
                dp[i] = dp[i - 1]
            else:
                dp[i] = dp[i - C - 1] + 1
        if dp[i - 1] > dp[i]:
            dp[i] = dp[i - 1]
    return dp


dp1 = compute(S)
dp2 = compute(S[::-1])[::-1]


def get_answers():
    for i in range(N):
        before = dp1[i - 1] if i else 0
        after = dp2[i + 1] if i < N - 1 else 0
        if before + after < K:
            yield i + 1


for x in get_answers():
    print(x)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k, c = na()
s = ns()

wp = []
for i in range(n):
    if s[i] == 'o':
        last = -99999 if len(wp) == 0 else wp[-1] + c
        if last < i:
            wp.append(i)

wf = []
for i in range(n-1, -1, -1):
    if s[i] == 'o':
        last = 99999999 if len(wf) == 0 else wf[-1] - c
        if last > i:
            wf.append(i)
wf = wf[::-1]

if len(wp) != k:
    sys.exit(0)

swp = set(wp)
for d in wf:
    if d in swp:
        print(d+1)

Submission status: Runtime Error

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,k,c=sep()
s=input()
c1=[0]*(n+5)
c2=[0]*(n+5)
for i in range(n):
    if s[i]=="x":
        c1[i]=c1[i-1]
    else:
        c1[i]=max(c1[i-1],c1[i-c-1]+1)
for i in range(n-1,-1,-1):
    if s[i]=="x":
        c2[i]=c2[i+1]
    else:
        c2[i]=max(c2[i+1],c2[i+c+1]+1)
ans=[]
if c2[1]==k-1 and s[0]=="o":
    ans.append(1)

for i in range(1,n-1):
    if s[i]=="x":
        continue
    if c1[i-1] + c2[i+1]==k-1:
        ans.append(i+1)

if n!=1:
    if c1[n-2]==k-1 and s[0]=="o":
        ans.append(n)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,k,c=sep()
s=input()
c1=[0]*(n+5)
c2=[0]*(n+5)
for i in range(n):
    if s[i]=="x":
        c1[i]=c1[i-1]
    else:
        c1[i]=c1[i-c-1]+1
for i in range(n-1,-1,-1):
    if s[i]=="x":
        c2[i]=c2[i+1]
    else:
        c2[i]=c2[i+c+1]+1
ans=[]
if c2[1]==k-1 and s[0]=="o":
    ans.append(1)

for i in range(1,n-1):
    if s[i]=="x":
        continue
    if c1[i-1] + c2[i+1]==k-1:
        ans.append(i+1)

if c1[n-2]==k-1 and s[0]=="o":
    ans.append(n)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import bisect
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=[-1]*N
a=1
o=list()
for i in range(N):
  if S[i]=="o":
    o.append(i)
for i in range(N):
  a= bisect.bisect_left(o, i+C+1)
  if a>=len(o):
    break
  ans[i]=o[a]
  if i+C+1>o[-1]:
    ans[i]=-1
po=[-1]*N
b=1
for i in range(N):
  if i+1>o[b]:
    b+=1
  if b>=len(o):
    break
  po[i]=o[b]
for i in range(N):
  ind=N-i-1
  if ans[ind]==-1:
    ans[ind]=list()
  else:
    ans[ind]=[ans[ind]]+ans[ans[ind]]
a=1
for k in L:
  nisu=a
  if k+1==N:
    print(k+1)
    break
  if len(ans[po[k]])+a!=K:
    print(k+1)
  a+=1

Submission status: Runtime Error

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]]
    G = {OK[0]:1}
    for i in range(1,len(OK)):
        x = OK[i]
        if x - greeds[-1] > C:
            greeds.append(x)
            G[x] = len(greeds)
        
        if len(greeds) == K: # ? 
            break
    
    # print(greeds)
    ans = []
    for i,x in enumerate(greeds): # xなしで成り立つかどうか調べる
        available = -1
        new_list = [0]
        is_last = i == len(greeds) - 1
        for j in range(1,len(OK)):  
            _x = OK[j]
            if _x != x and (new_list[-1] == 0 or  _x - new_list[-1] > C):
                new_list.append(_x)
                if _x in G and not is_last:
                    # print("_x",_x)
                    # print("G",G[_x])
                    new_list = new_list[1:]
                    available = (K - G[_x] + 1) + len(new_list) - 1
                    assert available >= 0
                    break
        
        if available == -1:
            new_list = new_list[1:]
            available = len(new_list)
        
        # print(x,available)
        if available < K:
            ans.append(x)

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





        




if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

work_day_min = []
work_day_max = []

for i in range(N):
    if S[i] == 'o':
        if i == 0 or i - work_day_min[-1] > C:
            work_day_min.append(i)
    if len(work_day_min) == K:
        break

for i in range(N):
    if S[N - i - 1] == 'o':
        if i == 0 or work_day_max[-1] - (N - i - 1) > C:
            work_day_max.append(N - i - 1)
    if len(work_day_max) == K:
        break

work_day_max.reverse()

for i in range(K):
    if work_day_min[i] == work_day_max[i]:
        print(work_day_min[i]+1)

Submission status: Runtime Error

Solution code:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

template <typename T>
void print(const vector<T> &v) {
    for (auto e : v) cout << e << ' ';
    cout << endl;
}

//------------------------- Libraries -------------------------//

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<1000000007>;

//--------------------------- Solve ---------------------------//

void solve() {
    int N, K, C; cin >> N >> K >> C;
    string s; cin >> s;
    s = '#' + s;
    vector<int> left(K+1), right(K+1);

    int cnt = 1;
    for (int i = 1; i <= N; i++) {
        if(s[i] == 'o') {
            left[cnt] = i;
            cnt++;
            i += C;
        }
    }
    cnt = K;
    for (int i = N; i >= 0 && cnt >= 0; i--) {
        if (s[i] == 'o') {
            right[cnt] = i;
            cnt--;
            i -= C;
        }
    }

    vector<int> ans;
    for (int i = 1; i <= K; i++) {
        if (left[i] == right[i]) ans.push_back(left[i]);
    }

    print(ans);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k, c_yutori = tin()
	s = input()
	can_work = [0]*n
	can_work[0] = 1 if s[0]=='o' else 0
	yn = c_yutori if s[0]=='o' else 0
	for i, c in enumerate( list(s)[1:],1):
		if yn == 0 and c == 'o':
			can_work[i] = can_work[i-1]+1
			yn = c_yutori
		else:
			can_work[i] = can_work[i-1]
			yn = max(0, yn - 1)
	need_to_work = [k]*n
	if s[-1]=='o':
		need_to_work[-1] = k-1
		yn = c_yutori
	else:
		need_to_work[-1]=k
		yn=0
	for i, c in enumerate(list(s)[-2::-1],1):
		pos = n-i-1
		if yn == 0 and c == 'o':
			need_to_work[pos] = need_to_work[pos+1]-1
			yn = c_yutori
		else:
			need_to_work[pos]=need_to_work[pos+1]
			yn = max(0, yn-1)
	#pa(can_work)
	#pa(need_to_work)
	if need_to_work[1] == 1:
		print(1)
		
	for i in range(1, n-1):
		if can_work[i-1] < need_to_work[i+1]:
			print(i+1)
		
	if can_work[-2]==k-1:
		print(n)
		
		
		
			
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

l2 = [0] * k
cnt2 = k - 1
future_work = 1e6

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

    if cnt2 != -1:
        if s[n-i] == 'x':
            continue
        if future_work - (n-i+1) > c:
            l2[cnt] = (n-i+1)
            cnt -= 1
            future_work = (n-i+1)
    if cnt == k and cnt2 == -1:
        break
for i in l:
    if i in l2:
        print(i)

Submission status: Runtime Error

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 s[i-1] == 'x':
        continue
    if i - last_work > c:
        l[cnt] = i
        cnt += 1
        last_work = i

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

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

Submission status: Runtime Error

Solution code:
n,k,c = map(int,input().split())
s = [i == "o" for i in list(input())]
i = 0
cnt = 0
l = [0]*n
r = [0]*n
while i < n:
    if s[i]:
        cnt += 1
        for j in range(i,c+i+1):
            if j < n:
                l[j] = cnt
        i += c+1
    else:
        l[i] = cnt
        i += 1
i = n-1
cnt = 0
while i >= 0:
    if s[i]:
        cnt += 1
        for j in range(i,i-1-c,-1):
            if j >= 0:
                r[j] = cnt
        i -= c+1
    else:
        r[i] = cnt
        i -= 1
#print(l,r)
if r[1] < k:
    print(1)
for i in range(1,n-1):
    if not s[i]:
        continue
    if l[i-1] + r[i+1] < k:
        print(i+1)
if l[n-2] < k:
    print(n)

Submission status: Runtime Error

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
        if i!=0:
            while i-j>=1:
                j+=1
                if left[i-j] != 0:
                    cl = left[i-j]
                    cl_i = i-j
                    break
        else:
            cl_i=-c
        
        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
        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: Runtime Error

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
        if i!=0:
            while i-j>=0:
                j+=1
                if left[i-j] != 0:
                    cl = left[i-j]
                    cl_i = i-j
                    break
        else:
            cl_i=-c
        
        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
        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: Runtime Error

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
        if i!=0:
            while i-j>=0:
                j+=1
                if left[i-j] != 0:
                    cl = left[i-j]
                    cl_i = i-j
                    break
        else:
            cl_i=-c
        
        if i!=n-1:
            while i+h <= n-1:
                h+=1
                if right[i+h] != 0:
                    cr = right[i+h]
                    cr_i = i+h
                    break
        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: Runtime Error

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
        if i!=0:
            while i-j>=0:
                j+=1
                if left[i-j] != 0:
                    cl = left[i-j]
                    cl_i = i-j
                    break
        else:
            cl_i=-c
        
        if i!=n-1:
            while i+h <= n-1:
                h+=1
                if right[i+h] != 0:
                    cr = right[i+h]
                    cr_i = i+h
                    break
        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: Runtime Error

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

r=0
arr1=[]
for i in range(n):
    if s[i]=='o' and (r>=c or i==0):
        arr1.append(i+1)
        r=0
        
    else:
        r+=1

r=0
arr2=[]
for i in reversed(range(n)):
    if s[i]=='o' and (r>=c or i==n-1):
        arr2.insert(0,i+1)
        r=0
        
    else:
        r+=1
ans=[]
for i in range(len(arr1)):
    if arr1[i]==arr2[i]:
        ans.append(arr1[i])

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
n,k,c=map(int,input().split())
s=input()
r=0
arr1=[]
for i in range(n):
    if s[i]=='o' and (r>=c or i==0):
        arr1.append(i+1)
        r=0
        
    else:
        
        r+=1

r=0
arr2=[]
for i in reversed(range(n)):
    if s[i]=='o' and (r>=c or i==n-1):
        arr2.insert(0,i+1)
        r=0
        
    else:
        r+=1
ans=[]
for i in range(len(arr1)):
    if arr1[i]==arr2[i]:
        ans.append(arr1[i])

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
n,k,c=map(int,input().split())
s=input()
r=0
arr1=[]
for i in range(n):
    if s[i]=='o' and (r>=c or i==0):
        arr1.append(i+1)
        r=0
        
    else:
        
        r+=1

r=0
arr2=[]
for i in reversed(range(n)):
    if s[i]=='o' and (r>=c or i==n-1):
        arr2.insert(0,i+1)
        r=0
        
    else:
        r+=1
ans=[]
for i in range(len(arr1)):
    if arr1[i]==arr2[i]:
        ans.append(arr1[i])
print(arr1)
print(arr2)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
line1 = input().split()
n = int(line1[0])
k = int(line1[1])
c = int(line1[2])
s = list(input())
t = s[::-1]
l = [s.index("o") + 1]
r = [len(s) - t.index("o")]
for i in range(1, k):
  j = l[i - 1]
  m = r[i - 1]
  while j - l[i - 1] <= c or s[j] != "o":
    j += 1
  while r[i - 1] - m <= c or t[m] != "o":
    m -= 1
  r.append(m + 1)
  l.append(j + 1)
d = set(r) & set(l)
for i in d:
  print(i)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, k, c = inp()
        st = inst()
        front, end = [], []
        def get(now, ans):
            if len(ans) == k:
                return
            for i in range(now, n):
                if st[i]=='o':
                    ans.append(i+1)
                    return get(i+1+c, ans)
        get(0, front)
        st = st[::-1]
        get(0, end)
        for i in range(len(end)):
            end[i] = n-end[i]+1
        end.sort()
        if len(front)!=k or len(end)!=k:
            return
        ans = []
        # print front, end
        for i in range(k):
            if front[i] == end[i]:
                ans.append(front[i])
        print '\n'.join(map(str, ans))

my_main()