結果
| 問題 |
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;
}