結果

問題 No.154 市バス
ユーザー lam6er
提出日時 2025-04-16 00:15:47
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,386 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 80,136 KB
最終ジャッジ日時 2025-04-16 00:17:33
合計ジャッジ時間 1,399 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 1
other WA * 2 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #

def solve():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    
    for S in cases:
        # Check counts of R and G
        count_R = S.count('R')
        count_G = S.count('G')
        if count_R != count_G:
            print("impossible")
            continue
        
        # Precompute prefix sum of W's
        n = len(S)
        prefix = [0] * n
        current = 0
        for i in range(n):
            if S[i] == 'W':
                current += 1
            prefix[i] = current
        
        stack = []
        possible = True
        # Iterate from the end to the start
        for i in reversed(range(n)):
            c = S[i]
            if c == 'R':
                stack.append(i)
            elif c == 'G':
                if not stack:
                    possible = False
                    break
                # Pop the R
                r_pos = stack.pop()
                # Check if there's at least one W before this G
                if i == 0:
                    possible = False
                    break
                if prefix[i-1] < 1:
                    possible = False
                    break
        # After processing all characters, stack should be empty
        if stack:
            possible = False
        
        print("possible" if possible else "impossible")
        
solve()
0