結果

問題 No.1313 N言っちゃダメゲーム (4)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:52:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 2,358 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 81,892 KB
最終ジャッジ日時 2025-03-20 18:53:10
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing

    def update_point(self, index, value):
        # Convert to 1-based index
        i = index + 1  # since input is 0-based
        while i <= self.n + 1:
            self.tree[i] += value
            i += i & -i

    def query_prefix(self, index):
        # Get sum from [0..index] (0-based)
        res = 0
        i = index + 1  # convert to 1-based
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def range_query(self, l, r):
        if l > r:
            return 0
        return self.query_prefix(r) - self.query_prefix(l - 1)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr +=1

    # Initialize valid array
    valid = [False] * N
    valid[0] = True  # 0 is not dangerous
    for i in range(1, N):
        valid[i] = (S[i-1] == 'o')

    fenwick = FenwickTree(N)
    lose = [False] * N

    for x in range(N-1, -1, -1):
        if not valid[x] or x >= N:
            lose[x] = True
        else:
            left = x + 1
            right = x + K
            if right >= N:
                right = N-1
            if left > right:
                # No possible moves
                lose[x] = True
            else:
                sum_good = fenwick.range_query(left, right)
                if sum_good > 0:
                    # There is at least one good position
                    lose[x] = False
                else:
                    lose[x] = True
        # Determine good[x] and update Fenwick tree
        good_val = 1 if (valid[x] and lose[x]) else 0
        # We need to set the value, not add, so we need to reset previous value
        # But since we are processing from high to low, each x is processed once.
        # Initially, all are 0. So delta is good_val - 0
        fenwick.update_point(x, good_val)
    
    # Collect the result
    result = []
    max_y = min(K, N-1)
    for y in range(1, max_y + 1):
        if valid[y] and lose[y]:
            result.append(y)
    if not result:
        print(0)
    else:
        for num in sorted(result):
            print(num)

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