結果
| 問題 | No.2226 Hello, Forgotten World! |
| ユーザー |
 OnjoujiToki
|
| 提出日時 | 2023-02-24 21:50:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 15 ms / 2,000 ms |
| コード長 | 6,488 bytes |
| コンパイル時間 | 1,680 ms |
| コンパイル使用メモリ | 140,440 KB |
| 最終ジャッジ日時 | 2025-02-10 20:53:16 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <unordered_map>#include <unordered_set>using namespace std;template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt &operator^=(long long p) { // quick_pow here:3ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(long long p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p;return ModInt(*this);} // added by QCFiumModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &p) {return os << p.x;}friend std::istream &operator>>(std::istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};long long mod_pow(long long x, int n, int p) {long long ret = 1;while (n) {/*∧,,,∧(· ̳• · • ̳)/··· づ♡ I love you*/if (n & 1) (ret *= x) %= p;(x *= x) %= p;n >>= 1;}return ret;}std::pair<std::vector<long long>, std::vector<int>> get_prime_factor_with_kinds(long long n) {std::vector<long long> prime_factors;std::vector<int> cnt; // number of i_th factorfor (long long i = 2; i <= sqrt(n); i++) {if (n % i == 0) {prime_factors.push_back(i);cnt.push_back(0);while (n % i == 0) n /= i, cnt[(int)prime_factors.size() - 1]++;}}if (n > 1) prime_factors.push_back(n), cnt.push_back(1);assert(prime_factors.size() == cnt.size());return {prime_factors, cnt};}template <typename T>struct SegmentTree {using Monoid = typename T::Monoid;explicit SegmentTree(int n) : SegmentTree(std::vector<Monoid>(n, T::id())) {}explicit SegmentTree(const std::vector<Monoid> &a) : n(a.size()), sz(1) {while (sz < n) sz <<= 1;data.assign(sz << 1, T::id());std::copy(a.begin(), a.end(), data.begin() + sz);for (int i = sz - 1; i > 0; --i) {data[i] = T::merge(data[i << 1], data[(i << 1) + 1]);}}void set(int idx, const Monoid val) {idx += sz;data[idx] = val;while (idx >>= 1)data[idx] = T::merge(data[idx << 1], data[(idx << 1) + 1]);}Monoid get(int left, int right) const {Monoid res_l = T::id(), res_r = T::id();for (left += sz, right += sz; left < right; left >>= 1, right >>= 1) {if (left & 1) res_l = T::merge(res_l, data[left++]);if (right & 1) res_r = T::merge(data[--right], res_r);}return T::merge(res_l, res_r);}Monoid operator[](const int idx) const { return data[idx + sz]; }private:const int n;int sz; // sz + 原数组坐标 = 线段树里的编号，1 basedstd::vector<Monoid> data;};namespace monoid {template <typename T>struct RangeMinimumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::max(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::min(a, b);}};template <typename T>struct RangeMaximumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::lowest(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::max(a, b);}};template <typename T>struct RangeSumQuery {using Monoid = T;static constexpr Monoid id() { return 0; }static Monoid merge(const Monoid &a, const Monoid &b) { return a + b; }};} // namespace monoid// using mint = ModInt<1000000007>;using mint = ModInt<998244353>;template <typename T>struct DSU {std::vector<T> f, siz;DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }T leader(T x) {while (x != f[x]) x = f[x] = f[f[x]];return x;}bool same(T x, T y) { return leader(x) == leader(y); }bool merge(T x, T y) {x = leader(x);y = leader(y);if (x == y) return false;siz[x] += siz[y];f[y] = x;return true;}T size(int x) { return siz[leader(x)]; }};void solve() {std::string sample = "helloworld";std::string s;int n;std::cin >> n;std::cin >> s;std::set<std::string> st;for (int i = n - 10; i >= 0; i--) {auto a = s.substr(i, 10);// std::cout << a << '\n';bool ok = true;for (int j = 0; j < (int)a.length(); j++) {if (a[j] == sample[j] or a[j] == '?')continue;else {ok = false;}}if (ok) {auto ns = s.substr(0, i) + s.substr(i, 10) + s.substr(i + 10);// std::cout << "before" << ns << '\n';for (int j = i; j < i + 10; j++) {ns[j] = sample[j - i];}for (int j = 0; j < n; j++) {if (ns[j] == '?') ns[j] = 'a';}// std::cout << "after" << ns << '\n';st.insert(ns);}}if (st.empty()) {std::cout << -1 << '\n';} else {std::cout << *st.begin() << '\n';}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) solve();return 0;}