結果
| 問題 |
No.996 Phnom Penh
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:58:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,119 bytes |
| コンパイル時間 | 574 ms |
| コンパイル使用メモリ | 74,324 KB |
| 実行使用メモリ | 16,072 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:37 |
| 合計ジャッジ時間 | 11,637 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 TLE * 1 -- * 3 |
ソースコード
#include <iostream>
#include <string>
#include <vector> // Used for std::vector but not essential here, string manipulation is enough
#include <numeric> // Not used, can remove include
/**
* @brief Applies Operation 2 to the given string `s`.
*
* Operation 2 consists of two steps:
* 1. Remove all occurrences of the character 'h' from the string.
* 2. Replace all occurrences of the character 'e' with 'h' in the resulting string.
*
* The operation is considered valid only if the string changes as a result.
* The function modifies the string `s` in place.
*
* @param s The string to apply Operation 2 on. Passed by reference and modified.
* @return true If the string `s` was changed by the operation.
* @return false If the string `s` remained unchanged after the operation.
*/
bool apply_op2(std::string& s) {
// Keep a copy of the original string to compare later and determine if the string changed.
std::string original_s = s;
// Step 1: Create an intermediate string `next_s` by removing all 'h' characters from `s`.
std::string next_s = "";
// Optimization: Reserve memory for `next_s` roughly equivalent to the current string length.
// This can reduce the number of memory reallocations needed as `next_s` grows.
next_s.reserve(s.length());
for (char c : s) { // Iterate through each character of the input string `s`
if (c != 'h') { // If the character is not 'h'
next_s += c; // Append it to the intermediate string `next_s`
}
}
// Clear the original string `s` to prepare for rebuilding it based on `next_s`.
s.clear();
// Optimization: Reserve memory for the final string `s`. Its length will be exactly the length of `next_s`.
s.reserve(next_s.length());
// Step 2: Rebuild `s` from `next_s`. Replace 'e' characters with 'h'.
for (char c : next_s) { // Iterate through each character of the intermediate string `next_s`
if (c == 'e') { // If the character is 'e'
s += 'h'; // Append 'h' to the final string `s`
} else { // For any other character
s += c; // Append the character itself to `s`
}
}
// Return true if the final string `s` is different from the `original_s`.
// This indicates that Operation 2 successfully changed the string.
return s != original_s;
}
int main() {
// Optimize standard C++ I/O operations for speed.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::string s; // Declare a string variable to store the input.
std::cin >> s; // Read the input string from standard input.
long long op_count = 0; // Initialize a counter for the total number of operations performed. Using long long for potentially large counts.
std::string target = "phnom"; // The substring to search for in Operation 1.
std::string replacement = "penh"; // The string to replace "phnom" with in Operation 1.
// Main loop: continues as long as operations can be performed that change the string.
// This implements a greedy strategy: prioritize Op1, then try Op2 if Op1 is not possible.
while (true) {
// --- Try Operation 1 ---
// Find the starting position (`pos`) of the first occurrence of the target substring "phnom".
// `std::string::npos` is returned if the substring is not found.
size_t pos = s.find(target);
// Check if "phnom" was found in the string `s`.
if (pos != std::string::npos) {
// If "phnom" is found, perform Operation 1: replace it with "penh".
// `s.replace(pos, target.length(), replacement)` replaces the substring of length `target.length()` starting at `pos` with `replacement`.
s.replace(pos, target.length(), replacement);
op_count++; // Increment the operation counter.
// After successfully applying Op1, restart the `while` loop immediately using `continue`.
// This ensures that we always check for Op1 possibilities first after any change.
continue;
}
// --- If Op1 was not possible, Try Operation 2 ---
// Before attempting Op2, check if the string contains 'h' or 'e'.
// Op2 requires at least one 'h' to remove or one 'e' to replace with 'h' to potentially change the string.
// If neither 'h' nor 'e' exists, Op2 cannot change the string.
bool has_h_or_e = false; // Flag to track if 'h' or 'e' is present.
for(char c : s) { // Iterate through the characters of the string `s`.
if (c == 'h' || c == 'e') { // If 'h' or 'e' is found
has_h_or_e = true; // Set the flag to true.
break; // Exit the loop early as we've confirmed presence.
}
}
// Proceed with Op2 only if 'h' or 'e' was found in the string.
if (has_h_or_e) {
// Attempt to apply Op2. The function `apply_op2` modifies `s` in place.
// It returns `true` if the string was changed, `false` otherwise.
if (apply_op2(s)) {
op_count++; // If Op2 successfully changed the string, increment the operation counter.
// After successfully applying Op2, restart the `while` loop using `continue`.
// This allows checking if Op2 created new opportunities for Op1.
continue;
}
}
// --- Termination Condition ---
// If the code reaches this point, it implies that:
// 1. Operation 1 ("phnom" -> "penh") could not be applied (no "phnom" found).
// 2. AND Operation 2 either was not applicable (no 'h' or 'e') or was applied but did not change the string.
// In this state, no further operations can modify the string according to the rules.
// Therefore, break out of the `while` loop.
break;
}
// Print the final total count of operations performed.
std::cout << op_count << std::endl;
return 0; // Indicate successful program execution.
}