結果

問題 No.154 市バス
ユーザー lam6er
提出日時 2025-03-20 20:39:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,090 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 80,716 KB
最終ジャッジ日時 2025-03-20 20:39:14
合計ジャッジ時間 1,757 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 2 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    T = int(data[0])
    cases = data[1:T+1]
    
    for S in cases:
        # Step 1: Check if number of Gs equals number of Rs
        g_positions = []
        r_positions = []
        for i, c in enumerate(S):
            if c == 'G':
                g_positions.append(i)
            elif c == 'R':
                r_positions.append(i)
        
        if len(g_positions) != len(r_positions):
            print("impossible")
            continue
        
        # Step 2: Check each R has at least one G before it
        valid = True
        for r in r_positions:
            has_g = False
            for g in g_positions:
                if g < r:
                    has_g = True
                    break
            if not has_g:
                print("impossible")
                valid = False
                break
        if not valid:
            continue
        
        # Step 3: Check that at any point, number of Gs <= Ws
        w_count = 0
        g_count = 0
        valid_step3 = True
        for c in S:
            if c == 'W':
                w_count += 1
            elif c == 'G':
                g_count += 1
                if g_count > w_count:
                    valid_step3 = False
                    break
        if not valid_step3:
            print("impossible")
            continue
        
        # Step 4: Pair each R with a G using greedy approach
        # Sort positions
        g_sorted = sorted(g_positions)
        r_sorted = sorted(r_positions)
        g_ptr = len(g_sorted) - 1
        possible = True
        
        for r in reversed(r_sorted):
            # Find the latest G that is before r
            while g_ptr >= 0 and g_sorted[g_ptr] >= r:
                g_ptr -= 1
            if g_ptr < 0:
                possible = False
                break
            g_ptr -= 1  # Mark this G as used
        
        if possible:
            print("possible")
        else:
            print("impossible")

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