結果

問題 No.154 市バス
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:48:13
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,448 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 80,860 KB
最終ジャッジ日時 2025-06-12 20:50:23
合計ジャッジ時間 1,910 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 2 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    
    for S in cases:
        r_count = S.count('R')
        g_count = S.count('G')
        w_count = S.count('W')
        
        # Check if number of R and G are equal
        if r_count != g_count:
            print("impossible")
            continue
        
        # Check if there are enough W for each pair
        if w_count < r_count:
            print("impossible")
            continue
        
        # Collect positions of G and R
        g_positions = []
        for i, c in enumerate(S):
            if c == 'G':
                g_positions.append(i)
        r_positions = [i for i, c in enumerate(S) if c == 'R']
        
        # Check if each R can be paired with a G that comes before it
        possible = True
        used = [False] * len(g_positions)
        # Process R in reverse order (from last to first)
        for r in reversed(r_positions):
            # Find the largest G position less than r
            idx = bisect_left(g_positions, r) - 1
            # Find the first unused G before r
            while idx >= 0 and used[idx]:
                idx -= 1
            if idx < 0:
                possible = False
                break
            used[idx] = True
        
        print("possible" if possible else "impossible")

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