結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー Andrew8128
提出日時 2025-08-10 17:41:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 509 ms / 2,000 ms
コード長 2,224 bytes
コンパイル時間 493 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 94,216 KB
最終ジャッジ日時 2025-11-01 09:58:17
合計ジャッジ時間 18,893 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def prepare(N, S):
    # csum_count[i] = [非 'w'/'a' の数, 'w'/'a' の数] の累積
    csum_count = [[0, 0] for _ in range(N + 1)]
    for i in range(N):
        if S[i] == 'w' or S[i] == 'a':
            csum_count[i + 1] = [csum_count[i][0], csum_count[i][1] + 1]
        else:
            csum_count[i + 1] = [csum_count[i][0] + 1, csum_count[i][1]]
    return csum_count


def solve(N, Q, S, T, X, csum_count):
    ans = ['?'] * Q
    for i in range(Q):
        X[i] -= 1  # 1-indexed → 0-indexed
        T[i] = min(T[i], 60)  # 60以上は不要

        # 二分探索
        l, r = 0, N + 1
        while l + 1 < r:
            c = (l + r) // 2
            if csum_count[c][1] < (X[i] - csum_count[c][0]) // (5 * (1 << T[i]) - 4):
                l = c
            elif csum_count[c][0] + csum_count[c][1] * (5 * (1 << T[i]) - 4) <= X[i]:
                l = c
            else:
                r = c

        if csum_count[l][0] + csum_count[l][1] * (5 * (1 << T[i]) - 4) == X[i]:
            ans[i] = S[l]
        else:
            X[i] -= csum_count[l][0] + csum_count[l][1] * (5 * (1 << T[i]) - 4)
            target = S
            cursor = l
            T[i] -= 1
            while X[i] != 0 and T[i] >= 0:
                if target[cursor] == 'a':
                    target = "answer"
                elif target[cursor] == 'w':
                    target = "warong"
                else:
                    break  # 異常終了

                cursor = 0
                while X[i] != 0:
                    if target[cursor] != 'w' and target[cursor] != 'a':
                        X[i] -= 1
                    elif X[i] < 5 * (1 << T[i]) - 4:
                        break
                    else:
                        X[i] -= 5 * (1 << T[i]) - 4
                    cursor += 1
                T[i] -= 1

            ans[i] = target[cursor]
    return ''.join(ans)


def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = input()
    T = []
    X = []
    for _ in range(Q):
        t, x = map(int, input().split())
        T.append(t)
        X.append(x)
    print(solve(N, Q, S, T, X, prepare(N, S)))


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