結果

問題 No.2231 Surprising Flash!
ユーザー tree_splaytree_splay
提出日時 2023-02-24 23:15:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,637 bytes
コンパイル時間 2,194 ms
コンパイル使用メモリ 209,508 KB
実行使用メモリ 61,072 KB
最終ジャッジ日時 2023-10-11 08:59:25
合計ジャッジ時間 9,211 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 4 ms
4,352 KB
testcase_02 WA -
testcase_03 AC 257 ms
4,348 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 57 ms
4,348 KB
testcase_09 WA -
testcase_10 AC 67 ms
4,348 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
権限があれば一括ダウンロードができます

ソースコード

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<res.size(); i++)
			res[i] += S[i+1] - S[i-M+1];

		int st = -1;
		for(int i=M-1; i<res.size(); 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