結果

問題 No.2231 Surprising Flash!
ユーザー tree_splaytree_splay
提出日時 2023-02-24 23:19:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,619 bytes
コンパイル時間 2,247 ms
コンパイル使用メモリ 204,476 KB
最終ジャッジ日時 2025-02-10 22:44:50
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 10 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long

void fast_fourier_transform(vector<complex<double>> &a, const bool invert = false){ // O(n log n)
  int n = (int)a.size();
  for(auto i = 1, j = 0; i < n; ++ i){
    int bit = n >> 1;
    for(; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if(i < j) swap(a[i], a[j]);
  }
  for(auto len = 1; len < n; len <<= 1){
    double theta = acos(-1) / len * (invert ? -1 : 1);
    complex<double> w(cos(theta), sin(theta));
    for(auto i = 0; i < n; i += len << 1){
      complex<double> wj(1);
      for(auto j = 0; j < len; ++ j, wj *= w){
        complex<double> u = a[i + j], v = wj * a[i + j + len];
        a[i + j] = u + v, a[i + j + len] = u - v;
      }
    }
  }
  if(invert){
    double inv_n = 1.0 / n;
    for(auto &x: a) x *= inv_n;
  }
}
template<class T>
vector<T> convolute(const vector<T> &p, const vector<T> &q){
  if(min(p.size(), q.size()) < 250){
    vector<T> res((int)p.size() + (int)q.size() - 1);
    for(size_t i = 0; i < p.size(); ++ i) for(size_t j = 0; j < q.size(); ++ j) res[i + j] += p[i] * q[j];
    return res;
  }
  vector<complex<double>> f(p.begin(), p.end()), g(q.begin(), q.end());
  int m = max(int(p.size()) + int(q.size()) - 1, 1), n = m;
  if(__builtin_popcount(n) != 1) n = 1 << __lg(n) + 1;
  f.resize(n), g.resize(n);
  fast_fourier_transform(f), fast_fourier_transform(g);
  for(auto i = 0; i < n; ++ i) f[i] *= g[i];
  fast_fourier_transform(f, true);
  vector<T> res(m);
  for(auto i = 0; i < m; ++ i) res[i] = round(f[i].real());
  return res;
}

int T;
int N, M;
string s, t;
int S[500501];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cin >> T;
	while(T--)
	{
		cin >> N >> M >> s >> t;
		reverse(t.begin(), t.end());

		for(int i=1; i<=N; i++)
			S[i] = S[i-1] + (s[i-1] == '?');

		vector<int> res(N+M-1);
		for(char c='a'; c<='z'; c++)
		{
			vector<int> A(N), B(M);

			for(int i=0; i<s.size(); i++)
				A[i] = (s[i] == c);
			for(int i=0; i<t.size(); i++)
				B[i] = (t[i] == c);

			auto C = convolute(A, B);
			assert(res.size() == C.size());

			for(int i=M-1; i<C.size(); i++)
				res[i] += C[i];
		}

		for(int i=M-1; i<N; i++)
			res[i] += S[i+1] - S[i-M+1];

		int st = -1;
		for(int i=M-1; i<N; i++)
			if (res[i] == M)
				st = i-M+1;
		if (st == -1) { cout << "-1\n"; continue; }

		reverse(t.begin(), t.end()); //
		for(int i=st; i<st+M; i++)
		{
			assert(s[i] == '?' || s[i] == t[i-st]);
			s[i] = t[i-st];
		}

		for(int i=0; i<N; i++)
			if (s[i] == '?')
				s[i] = 'a';

		cout << s << "\n";
	}
	return 0;
}
0