結果
| 問題 | No.2231 Surprising Flash! |
| ユーザー |
 apricity
|
| 提出日時 | 2023-05-04 09:09:51 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 771 ms / 4,000 ms |
| コード長 | 6,539 bytes |
| コンパイル時間 | 3,038 ms |
| コンパイル使用メモリ | 181,964 KB |
| 最終ジャッジ日時 | 2025-02-12 16:50:44 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 44 |
ソースコード
#include<iostream>#include<string>#include<vector>#include<algorithm>#include<numeric>#include<cmath>#include<utility>#include<tuple>#include<cstdint>#include<cstdio>#include<iomanip>#include<map>#include<queue>#include<set>#include<stack>#include<deque>#include<unordered_map>#include<unordered_set>#include<bitset>#include<cctype>#include<chrono>#include<random>#include<cassert>#include<cstddef>#include<iterator>#include<string_view>#include<type_traits>#ifdef LOCAL# include "debug_print.hpp"# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define debug(...) (static_cast<void>(0))#endifusing namespace std;#define rep(i,n) for(int i=0; i<(n); i++)#define rrep(i,n) for(int i=(n)-1; i>=0; i--)#define FOR(i,a,b) for(int i=(a); i<(b); i++)#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)#define ALL(v) v.begin(), v.end()#define RALL(v) v.rbegin(), v.rend()#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );#define pb push_backusing ll = long long;using D = double;using LD = long double;using P = pair<int, int>;template<typename T> using PQ = priority_queue<T,vector<T>>;template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }void yesno(bool flag) {cout << (flag?"Yes":"No") << "\n";}template<typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template<typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template<typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}void in() {}template<typename T, class... U>void in(T &t, U &...u) {cin >> t;in(u...);}void out() { cout << "\n"; }template<typename T, class... U, char sep = ' '>void out(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;out(u...);}void outr() {}template<typename T, class... U, char sep = ' '>void outr(const T &t, const U &...u) {cout << t;outr(u...);}#include "atcoder/convolution.hpp"#include "atcoder/string.hpp"/*** @brief Sparse-Table(スパーステーブル)* @docs docs/sparse-table.md*/template< typename T, typename F >struct SparseTable {F f;vector< vector< T > > st;vector< int > lookup;SparseTable() = default;explicit SparseTable(const vector< T > &v, const F &f) : f(f) {const int n = (int) v.size();const int b = 32 - __builtin_clz(n);st.assign(b, vector< T >(n));for(int i = 0; i < v.size(); i++) {st[0][i] = v[i];}for(int i = 1; i < b; i++) {for(int j = 0; j + (1 << i) <= n; j++) {st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);}}lookup.resize(v.size() + 1);for(int i = 2; i < lookup.size(); i++) {lookup[i] = lookup[i >> 1] + 1;}}inline T fold(int l, int r) const {int b = lookup[r - l];return f(st[b][l], st[b][r - (1 << b)]);}};template< typename T, typename F >SparseTable< T, F > get_sparse_table(const vector< T > &v, const F &f) {return SparseTable< T, F >(v, f);}void solve(){int n,m; string s,t; in(n,m,s,t);vector<ll> x3_cs(n+1),x_rev(n),x2_rev(n),y(m),y2(m);rep(i,n) {int val = (s[i] == '?' ? 0 : (s[i]-'a')+1);x3_cs[i+1] = x3_cs[i] + val*val*val;x_rev[n-1-i] = val;x2_rev[n-1-i] = val*val;}rep(i,m) {int val = (t[i]-'a')+1;y[i] = val;y2[i] = val*val;}vector<int> pos_match;auto xxy = atcoder::convolution_ll(x2_rev, y);auto xyy = atcoder::convolution_ll(x_rev, y2);rep(i,n-m+1) {ll sum = x3_cs[i+m] - x3_cs[i] - 2 * xxy[n-1-i] + xyy[n-1-i];if (sum == 0) pos_match.pb(i);}if (pos_match.empty()) {out("-1");return;}string sr = s;rep(i,n) if(sr[i] == '?') sr[i] = 'a';auto ztt = atcoder::z_algorithm(t);string u = t+sr;auto sa = atcoder::suffix_array(u);auto lc = atcoder::lcp_array(u, sa);vector<int> sa_inv(n+m);rep(i,n+m) sa_inv[sa[i]] = i;auto spt = get_sparse_table(lc, [](auto a, auto b){return min(a,b);});int idx = pos_match[0];FOR(i,1,pos_match.size()) {int pos = pos_match[i];if (idx+m <= pos) {int p = sa_inv[0], q = sa_inv[m+idx];if (p > q) swap(p,q);int len = spt.fold(p,q);if (len < m) {char a = t[len], b = sr[idx+len];if (a > b) {idx = pos;}continue;}p = sa_inv[0], q = sa_inv[m+pos];if (p > q) swap(p,q);len = spt.fold(p,q);if (len < m) {char a = t[len], b = sr[idx+len];if (a > b) {idx = pos;}continue;}}else {int p = sa_inv[0], q = sa_inv[m+idx];if (p > q) swap(p,q);int len = spt.fold(p,q);if (len < pos-idx) {char a = t[len], b = sr[idx+len];if (a > b) {idx = pos;}continue;}len = ztt[pos-idx];if (len < m-pos+idx) {char a = t[len+pos-idx], b = t[len];if (a > b) {idx = pos;}continue;}p = sa_inv[idx+m+m], q = sa_inv[m-pos+idx];if (p > q) swap(p,q);len = spt.fold(p,q);if (len < pos-idx) {char a = sr[len+idx+m], b = t[m-pos+idx+len];if (a > b) {idx = pos;}continue;}}}string ans = sr;rep(i,m) ans[i+idx] = t[i];out(ans);}int main(){ios_base::sync_with_stdio(false);cin.tie(nullptr);int ntcs; in(ntcs);while(ntcs--) {solve();}}