#1084096 (C++17) No.154 市バス

• 問題: No.154 市バス
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:18:54
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,454 bytes
• コンパイル時間: 709 ms
• コンパイル使用メモリ: 70,908 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:19:47
• 合計ジャッジ時間: 1,512 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	WA * 1
other	AC * 7 WA * 1

ソースコード

#include <iostream>
#include <string>
#include <vector> // Included for completeness, although not directly used in the final logic.

// Use standard namespace for brevity.
using namespace std; 

/*
Function to solve a single test case.
Input: Reads a string S from standard input. S represents the sequence of bus light colors observed.
Output: Returns "possible" if the sequence S is valid according to the rules, "impossible" otherwise.

The rules derived from the problem statement are:
1. Each bus route runs at least 3 buses daily: W...W G R. This means at least one W bus, then one G bus, then one R bus, in that order for each route.
2. Yuki observes ALL buses passing on a certain road from the first bus of the day to the very last bus.
3. The observed sequence S must be explainable by some combination of bus routes passing by.

Algorithm checks the following conditions dynamically:
- For every G bus encountered, there must be at least one 'available' W bus that appeared earlier. An available W bus is one that hasn't been designated as the required preceding W bus for another route yet.
- For every R bus encountered, there must be a pending G bus (from the same route implicitly) that appeared earlier.
- At the end of the sequence, all G buses must have been matched with subsequent R buses.
- Based on interpretation of "始発から終バスまで" (from first to last bus) and "いくつかの系統のバスが走っています" (several routes run), a sequence consisting only of W buses is considered impossible, as it implies no routes completed their service cycle.
*/
string solve() {
    string s; // The input sequence of observed light colors
    cin >> s;
    
    int open_G = 0;      // Counter for G buses seen for which the corresponding R has not yet been seen. Represents active routes in the G->R phase.
    int available_W = 0; // Counter for W buses seen so far that can potentially fulfill the 'at least one W before G' requirement for a route.
    bool has_non_W = false; // Flag to check if the string contains any character other than 'W'. Used to detect the edge case of a sequence with only Ws.
    
    // Process the sequence character by character
    for (char c : s) {
        if (c == 'W') {
            // A W bus passes. It could be one of the initial Ws for some route.
            // We increment the count of available Ws.
            available_W++;
        } else if (c == 'G') {
            // A G bus passes (second-to-last bus of some route).
            has_non_W = true; // Mark that a non-W character is present in the sequence.
            
            // This G must be preceded by at least one W bus from its route.
            // Check if there is any available W bus recorded so far.
            if (available_W > 0) {
                // Yes, there is at least one available W.
                // We assign one available W to this route. Decrease the count of available Ws.
                available_W--; 
                // This G starts the final phase (G -> R) for its route. Increment the count of open G requirements.
                open_G++;
            } else {
                // No available W bus encountered before this G.
                // This violates the condition that each route runs >= 3 buses (which implies at least one W before G).
                // The sequence is impossible.
                return "impossible";
            }
        } else if (c == 'R') { // Character must be 'R' based on problem constraints.
            // An R bus passes (last bus of some route).
            has_non_W = true; // Mark that a non-W character is present.
            
            // This R must follow a G bus from the same route.
            // Check if there is any pending G requirement (open_G > 0).
            if (open_G > 0) {
                // Yes, there is at least one G waiting for its R.
                // Match this R with one such G. Decrease the count of open G requirements.
                open_G--;
            } else {
                // This R appeared, but there's no pending G waiting for its R (open_G is 0).
                // This violates the required G -> R structure for any route.
                // The sequence is impossible.
                return "impossible";
            }
        }
        // The problem statement guarantees input contains only 'W', 'G', 'R'. No other character needs handling.
    }
    
    // After processing the entire string S:
    // Check if all G requirements have been met.
    if (open_G == 0) {
        // If open_G is 0, it means every G bus seen was eventually matched by an R bus later in the sequence.
        // This implies the total count of Gs equals the total count of Rs in the sequence.
        
        // Now, consider the edge case: a sequence consisting only of 'W's.
        // `has_non_W` flag helps detect this. If `has_non_W` is false, the string only had 'W's (or was empty).
        // Since the constraint is 1 <= |S|, an empty string isn't possible.
        // A non-empty string containing only 'W's seems impossible under the problem context:
        // Yuki observes from the first bus to the last bus, and several routes run. This implies G and R buses must appear.
        if (!has_non_W) { 
             // The string is non-empty (due to constraints) and contains only 'W's.
             return "impossible";
        } else {
             // The string contains Gs and Rs, and all checks passed:
             // - W requirement for each G met.
             // - G -> R order maintained for all routes.
             // - All Gs matched with Rs.
             // The sequence is possible.
             return "possible";
        }
    } else {
        // If open_G > 0, it means there were more G buses than R buses observed.
        // Some routes started their G phase but never finished with an R bus by the end of the sequence.
        // This contradicts the condition of observing until the "終バスまで" (last bus).
        // The sequence is impossible.
        return "impossible";
    }
}

int main() {
    // Optimize C++ standard input/output streams for speed.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t; // Number of test cases
    cin >> t;
    // Process each test case
    while (t--) {
        // Call the solve function for the current test case and print its result.
        cout << solve() << endl;
    }
    return 0;
}