結果
問題 |
No.2226 Hello, Forgotten World!
|
ユーザー |
|
提出日時 | 2023-02-24 22:58:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,146 bytes |
コンパイル時間 | 2,099 ms |
コンパイル使用メモリ | 198,336 KB |
最終ジャッジ日時 | 2025-02-10 22:08:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 9 |
ソースコード
#include <cctype> #ifndef SHO_LOCAL #include <bits/stdc++.h> #define debug(...) ; #else #include "debug.h" #endif #define all(x) (x).begin(), (x).end() #define lb(x, a) lower_bound(all(x), (a)) - (x).begin() typedef long long ll; using namespace std; static inline vector<int> z_algo(const string &s) { int n = (int)s.size(); vector<int> Z(n); int from = -1, until = -1; for (int i = 1; i < n; i++) { int &a = Z[i]; if (from != -1) { a = max(0, min(Z[i - from], until - i)); } while (i + a < n && (s[i + a] == s[a] || s[i + a] == '?' || s[a] == '?')) { a++; } if (until < i + a) { until = i + a; from = i; } } Z[0] = n; return Z; } int main() { iostream::sync_with_stdio(0), cin.tie(0); int T; cin >> T; int n; string s; const string S = "helloworld"; int m = (int)S.size(); while (T--) { cin >> n >> s; string t = S + s; auto Z = z_algo(t); n = (int)t.size(); int left = -1; for (int i = m; i < n; i++) { if (Z[i] >= 10) { left = i; break; } } if (left == -1) { cout << -1 << '\n'; continue; } int right = left; for (int i = m - 1; i > left; i--) { if (Z[i] >= 10) { right = i; break; } } int ans = right; if (left != right && left + 9 >= right) { int len = right + 10 - left; string temp = t.substr(left, len); int diff = right - left; for (int j = 0; j < m; j++) { temp[j + diff] = S[j]; } for (int j = 0; j < diff; j++) { if (temp[j] == '?') temp[j] = 'a'; } bool f = false; for (int j = 0; j < m; j++) { if (!f && temp[j] < S[j]) break; if (S[j] < temp[j]) { f = true; } temp[j] = S[j]; } for (int j = 0; j < len; j++) { t[left + j] = temp[j]; } } else { for (int j = 0; j < m; j++) { t[left + j] = S[j]; } } for (int j = 0; j < n; j++) { if (t[j] == '?') t[j] = 'a'; } cout << t.substr(m) << '\n'; } return 0; }