結果
問題 |
No.2226 Hello, Forgotten World!
|
ユーザー |
|
提出日時 | 2023-02-24 23:17:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,947 bytes |
コンパイル時間 | 2,303 ms |
コンパイル使用メモリ | 197,624 KB |
最終ジャッジ日時 | 2025-02-10 22:36:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 right = -1; for (int i = n - 1; i >= m; i--) { if (Z[i] >= 10) { right = i; break; } } if (right == -1) { cout << -1 << '\n'; continue; } for (int j = 0; j < n; j++) { if (t[j] == '?') { if (j >= right && j < right + m) { t[j] = S[j - right]; } else { t[j] = 'a'; } } } for (int i = right - 1; i >= m; i--) { if (Z[i] >= m) { bool ok = false; for (int j = 0; j < m; j++) { if (t[i + j] > S[j]) { ok = true; break; } if (t[i + j] < S[j]) { ok = false; break; } } if (ok) { for (int j = 0; j < m; j++) { t[i + j] = S[j]; } for (int j = i + m; j < n; j++) { t[j] = 'a'; } } } } debug(t); cout << t.substr(m) << '\n'; } return 0; }