結果

問題 No.154 市バス
ユーザー gew1fw
提出日時 2025-06-12 16:29:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,321 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 76,428 KB
最終ジャッジ日時 2025-06-12 16:29:25
合計ジャッジ時間 1,729 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 2 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #

def is_possible(S):
    n = len(S)
    count_G = S.count('G')
    count_R = S.count('R')
    count_W = S.count('W')
    
    if count_G != count_R:
        return False
    if count_W < count_G:
        return False
    
    # Precompute next_G and next_R
    next_G = [None] * n
    next_R = [None] * n
    last_G = None
    last_R = None
    
    for i in range(n-1, -1, -1):
        if S[i] == 'G':
            last_G = i
        next_G[i] = last_G
        
        if S[i] == 'R':
            last_R = i
        next_R[i] = last_R
    
    # Check condition3: each G has R after it
    for i in range(n):
        if S[i] == 'G':
            if i+1 >= n:
                return False
            if next_R[i+1] is None:
                return False
    
    # Check condition4: each W has G and R after it
    for i in range(n):
        if S[i] == 'W':
            if i+1 >= n:
                return False
            g_pos = next_G[i+1]
            if g_pos is None:
                return False
            if g_pos + 1 >= n:
                return False
            r_pos = next_R[g_pos + 1]
            if r_pos is None:
                return False
    return True

T = int(input())
for _ in range(T):
    S = input().strip()
    if is_possible(S):
        print("possible")
    else:
        print("impossible")
0