結果
| 問題 | No.2231 Surprising Flash! |
| ユーザー |
 maksim
|
| 提出日時 | 2023-02-24 23:09:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,318 ms / 4,000 ms |
| コード長 | 21,042 bytes |
| コンパイル時間 | 9,677 ms |
| コンパイル使用メモリ | 508,932 KB |
| 実行使用メモリ | 123,120 KB |
| 最終ジャッジ日時 | 2024-06-12 07:37:20 |
| 合計ジャッジ時間 | 48,766 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 44 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int maxn=1e6+5;int sp[maxn][20];template <typename T>vector<int> suffix_array(int n, const T &s, int char_bound) {vector<int> a(n);if (n == 0) {return a;}if (char_bound != -1) {vector<int> aux(char_bound, 0);for (int i = 0; i < n; i++) {aux[s[i]]++;}int sum = 0;for (int i = 0; i < char_bound; i++) {int add = aux[i];aux[i] = sum;sum += add;}for (int i = 0; i < n; i++) {a[aux[s[i]]++] = i;}} else {iota(a.begin(), a.end(), 0);sort(a.begin(), a.end(), [&s](int i, int j) { return s[i] < s[j]; });}vector<int> sorted_by_second(n);vector<int> ptr_group(n);vector<int> new_group(n);vector<int> group(n);group[a[0]] = 0;for (int i = 1; i < n; i++) {group[a[i]] = group[a[i - 1]] + (!(s[a[i]] == s[a[i - 1]]));}int cnt = group[a[n - 1]] + 1;int step = 1;while (cnt < n) {int at = 0;for (int i = n - step; i < n; i++) {sorted_by_second[at++] = i;}for (int i = 0; i < n; i++) {if (a[i] - step >= 0) {sorted_by_second[at++] = a[i] - step;}}for (int i = n - 1; i >= 0; i--) {ptr_group[group[a[i]]] = i;}for (int i = 0; i < n; i++) {int x = sorted_by_second[i];a[ptr_group[group[x]]++] = x;}new_group[a[0]] = 0;for (int i = 1; i < n; i++) {if (group[a[i]] != group[a[i - 1]]) {new_group[a[i]] = new_group[a[i - 1]] + 1;} else {int pre = (a[i - 1] + step >= n ? -1 : group[a[i - 1] + step]);int cur = (a[i] + step >= n ? -1 : group[a[i] + step]);new_group[a[i]] = new_group[a[i - 1]] + (pre != cur);}}swap(group, new_group);cnt = group[a[n - 1]] + 1;step <<= 1;}return a;}template <typename T>vector<int> suffix_array(const T &s, int char_bound) {return suffix_array((int) s.size(), s, char_bound);}template <typename T>vector<int> build_lcp(int n, const T &s, const vector<int> &sa) {assert((int) sa.size() == n);vector<int> pos(n);for (int i = 0; i < n; i++) {pos[sa[i]] = i;}vector<int> lcp(max(n - 1, 0));int k = 0;for (int i = 0; i < n; i++) {k = max(k - 1, 0);if (pos[i] == n - 1) {k = 0;} else {int j = sa[pos[i] + 1];while (i + k < n && j + k < n && s[i + k] == s[j + k]) {k++;}lcp[pos[i]] = k;}}return lcp;}template <typename T>vector<int> build_lcp(const T &s, const vector<int> &sa) {return build_lcp((int) s.size(), s, sa);}typedef long long ll;const int p=998244353;int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}int inv(int x) {return po(x,p-2);}#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <immintrin.h>#include <algorithm>#include <cstdint>#include <cstdio>#include <cstring>#include <vector>constexpr std::uint32_t MOD = 998244353, PRIMITIVE_ROOT = 3;const unsigned int MAX_N = 524288;std::uint32_t mod_mul(std::uint32_t a, std::uint32_t b) { return static_cast<std::uint64_t>(a) * b % MOD; }std::uint32_t pow(std::uint32_t a, std::uint32_t b) {std::uint32_t ret = 1;while (b) {if (b & 1) ret = mod_mul(ret, a);a = mod_mul(a, a);b >>= 1;}return ret;}__m256i mod_add_simd(__m256i a, __m256i b) {__m256i c = _mm256_add_epi32(a, b);__m256i d = _mm256_sub_epi32(c, _mm256_set1_epi32(MOD));__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), d);return _mm256_blendv_epi8(d, c, mask);}__m256i mod_sub_simd(__m256i a, __m256i b) {__m256i c = _mm256_sub_epi32(a, b);__m256i d = _mm256_add_epi32(c, _mm256_set1_epi32(MOD));__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), c);return _mm256_blendv_epi8(c, d, mask);}__m256i reduce_simd(__m256i a) {__m256i b = _mm256_sub_epi32(a, _mm256_set1_epi32(MOD));__m256i mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(0), b);return _mm256_blendv_epi8(b, a, mask);}__m256i add_simd(__m256i a, __m256i b) { return _mm256_add_epi32(a, b); }__m256i sub_simd(__m256i a, __m256i b) {__m256i c = _mm256_sub_epi32(a, b);return _mm256_add_epi32(c, _mm256_set1_epi32(MOD));}__m256i mulhi_simd(__m256i a, __m256i b) {__m256i a0 = _mm256_unpacklo_epi32(a, a);__m256i a1 = _mm256_unpackhi_epi32(a, a);__m256i b0 = _mm256_unpacklo_epi32(b, b);__m256i b1 = _mm256_unpackhi_epi32(b, b);__m256i c0 = _mm256_mul_epu32(a0, b0);__m256i c1 = _mm256_mul_epu32(a1, b1);return (__m256i)_mm256_shuffle_ps((__m256)c0, (__m256)c1, _MM_SHUFFLE(3, 1, 3, 1));}struct ConstMulSimd {__m256i a;__m256i a_div;explicit ConstMulSimd(std::uint32_t a) : a(_mm256_set1_epi32(a)) { a_div = _mm256_set1_epi32((std::uint64_t(a) << 32) / MOD); }ConstMulSimd(std::uint32_t a0, std::uint32_t a1, std::uint32_t a2, std::uint32_t a3, std::uint32_t a4, std::uint32_t a5, std::uint32_t a6, std::uint32_t a7) {a = _mm256_setr_epi32(a0, a1, a2, a3, a4, a5, a6, a7);std::uint32_t a_div0, a_div1, a_div2, a_div3, a_div4, a_div5, a_div6, a_div7;a_div0 = (std::uint64_t(a0) << 32) / MOD;a_div1 = (std::uint64_t(a1) << 32) / MOD;a_div2 = (std::uint64_t(a2) << 32) / MOD;a_div3 = (std::uint64_t(a3) << 32) / MOD;a_div4 = (std::uint64_t(a4) << 32) / MOD;a_div5 = (std::uint64_t(a5) << 32) / MOD;a_div6 = (std::uint64_t(a6) << 32) / MOD;a_div7 = (std::uint64_t(a7) << 32) / MOD;a_div = _mm256_setr_epi32(a_div0, a_div1, a_div2, a_div3, a_div4, a_div5, a_div6, a_div7);}__m256i mul(__m256i b) {__m256i q = mulhi_simd(a_div, b);__m256i c = _mm256_mullo_epi32(a, b);__m256i qm = _mm256_mullo_epi32(q, _mm256_set1_epi32(MOD));__m256i r = _mm256_sub_epi32(c, qm);return r;}__m256i mul_mod(__m256i b) {__m256i r = mul(b);return reduce_simd(r);}};void ntt(unsigned int n, std::uint32_t *a) {std::uint32_t w = pow(PRIMITIVE_ROOT, (MOD - 1) / n);unsigned int m = n;while (m >= 16) {unsigned int mh = m / 2;std::uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8;w0 = 1;w1 = w;w2 = mod_mul(w1, w1);w3 = mod_mul(w2, w1);w4 = mod_mul(w2, w2);w5 = mod_mul(w4, w1);w6 = mod_mul(w4, w2);w7 = mod_mul(w4, w3);w8 = mod_mul(w4, w4);ConstMulSimd wi_mul(w0, w1, w2, w3, w4, w5, w6, w7);for (unsigned int i = 0; i < n; i += m) {std::uint32_t wj = 1;for (unsigned int j = 0; j < mh; j += 8) {unsigned int j0 = i + j, j1 = j0 + mh;__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j0));__m256i x1 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j1));__m256i y0 = mod_add_simd(x0, x1);__m256i y1 = wi_mul.mul(sub_simd(x0, x1));ConstMulSimd wj_mul(wj);y1 = wj_mul.mul_mod(y1);_mm256_store_si256(reinterpret_cast<__m256i *>(a + j0), y0);_mm256_store_si256(reinterpret_cast<__m256i *>(a + j1), y1);wj = mod_mul(wj, w8);}}m = mh;w = w2;}std::uint32_t w0, w1, w2, w3;w0 = 1;w1 = w;w2 = mod_mul(w1, w1);w3 = mod_mul(w2, w1);ConstMulSimd mul_1(1, 1, 1, 1, w0, w1, w2, w3), mul_2(1, 1, w0, w2, 1, 1, w0, w2);for (unsigned int i = 0; i < n; i += 8) {__m256i x00, x01, x10, x11, x20, x21, x30, x31, x40, x41, x50, x51, x6;x00 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));x01 = _mm256_permute4x64_epi64(x00, 0b01001110);x10 = add_simd(x00, x01);x11 = sub_simd(x01, x00);x20 = mul_1.mul_mod(_mm256_blend_epi32(x10, x11, 0b11110000));x21 = _mm256_shuffle_epi32(x20, 0b01001110);x30 = add_simd(x20, x21);x31 = sub_simd(x21, x20);x40 = mul_2.mul_mod(_mm256_blend_epi32(x30, x31, 0b11001100));x41 = _mm256_shuffle_epi32(x40, 0b10110001);x50 = add_simd(x40, x41);x51 = sub_simd(x41, x40);x6 = reduce_simd(_mm256_blend_epi32(x50, x51, 0b10101010));_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), x6);}}void intt(unsigned int n, std::uint32_t *a) {std::vector<std::uint32_t> w_vec;std::uint32_t w = pow(PRIMITIVE_ROOT, MOD - 1 - (MOD - 1) / n);for (unsigned int i = n; i >= 16; i >>= 1) {w_vec.push_back(w);w = mod_mul(w, w);}std::uint32_t w0, w1, w2, w3;w0 = 1;w1 = w;w2 = mod_mul(w1, w1);w3 = mod_mul(w2, w1);ConstMulSimd mul_1(1, 1, 1, 1, w0, w1, w2, w3), mul_2(1, 1, w0, w2, 1, 1, w0, w2);for (unsigned int i = 0; i < n; i += 8) {__m256i x00, x01, x10, x11, x20, x21, x30, x31, x40, x41, x50, x51, x6;x00 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));x01 = _mm256_shuffle_epi32(x00, 0b10110001);x10 = add_simd(x00, x01);x11 = sub_simd(x01, x00);x20 = mul_2.mul_mod(_mm256_blend_epi32(x10, x11, 0b10101010));x21 = _mm256_shuffle_epi32(x20, 0b01001110);x30 = add_simd(x20, x21);x31 = sub_simd(x21, x20);x40 = mul_1.mul_mod(_mm256_blend_epi32(x30, x31, 0b11001100));x41 = _mm256_permute4x64_epi64(x40, 0b01001110);x50 = add_simd(x40, x41);x51 = sub_simd(x41, x40);x6 = reduce_simd(_mm256_blend_epi32(x50, x51, 0b11110000));_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), x6);}unsigned int m = 16;while (m <= n) {unsigned int mh = m / 2;std::uint32_t w = w_vec.back();w_vec.pop_back();std::uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8;w0 = 1;w1 = w;w2 = mod_mul(w1, w1);w3 = mod_mul(w2, w1);w4 = mod_mul(w2, w2);w5 = mod_mul(w4, w1);w6 = mod_mul(w4, w2);w7 = mod_mul(w4, w3);w8 = mod_mul(w4, w4);ConstMulSimd wi_mul(w0, w1, w2, w3, w4, w5, w6, w7);for (unsigned int i = 0; i < n; i += m) {std::uint32_t wj = 1;for (unsigned int j = 0; j < mh; j += 8) {unsigned int j0 = i + j, j1 = j0 + mh;__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j0));__m256i x1 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + j1));x1 = wi_mul.mul_mod(x1);ConstMulSimd wj_mul(wj);x1 = wj_mul.mul_mod(x1);__m256i y0 = mod_add_simd(x0, x1);__m256i y1 = mod_sub_simd(x0, x1);_mm256_store_si256(reinterpret_cast<__m256i *>(a + j0), y0);_mm256_store_si256(reinterpret_cast<__m256i *>(a + j1), y1);wj = mod_mul(wj, w8);}}m *= 2;}std::uint32_t n_inv = pow(n, MOD - 2);ConstMulSimd mul_n_inv(n_inv);for (unsigned int i = 0; i < n; i += 8) {__m256i x0 = _mm256_load_si256(reinterpret_cast<__m256i *>(a + i));_mm256_store_si256(reinterpret_cast<__m256i *>(a + i), mul_n_inv.mul_mod(x0));}}void convolution(unsigned int n, std::uint32_t *a, std::uint32_t *b) {ntt(n, a);ntt(n, b);for (unsigned int i = 0; i < n; i++) {a[i] = mod_mul(a[i], b[i]);}intt(n, a);}struct IO {const static unsigned int MAX_STDIO_SIZE = 10 * 2 * MAX_N + 14;char stdio_buf[MAX_STDIO_SIZE];std::uint32_t char_arr_to_int(std::uint64_t x) {x = (x >> 8) + x * 10;x = ((x >> 16) & 0x000000FF000000FFull) + (x & 0x000000FF000000FFull) * 100;x = (x >> 32) + x * 10000;return x & 0xFFFFFFFFull;}std::uint64_t int_to_char_arr(std::uint32_t x) {std::uint64_t r = x, q;q = ((r * 109951163) & 0xFFFFFF0000000000ull) >> 40;r = (r << 32) - q * 42949672959999ull;q = ((r * 10486) & 0xFFF00000FFF00000ull) >> 20;r = (r << 16) - q * 6553599ull;q = ((r * 103) & 0xFC00FC00FC00FC00ull) >> 10;r = (r << 8) - q * 2559ull;return r;}std::uint32_t read_int(char *&buf) {std::uint64_t x = *reinterpret_cast<std::uint64_t *>(buf);std::uint64_t space = ((x + 0x1010101010101010ull) & 0x4040404040404040) ^ 0x4040404040404040;if (space == 0) {std::uint32_t res = char_arr_to_int(x - 0x3030303030303030ull);if (buf[8] <= ' ') {buf += 9;} else {res = res * 10 + (buf[8] - '0');buf += 10;}return res;}unsigned int space_pos = __builtin_ffsll(space);std::uint64_t mask = (1ULL << (space_pos - 7)) - 1;std::uint32_t res = char_arr_to_int(((x - 0x3030303030303030ull) & mask) << (71 - space_pos));buf += (space_pos + 1) >> 3;return res;}void read(unsigned int &n, unsigned int &m, std::uint32_t *a, std::uint32_t *b) {std::fread(stdio_buf, 1, MAX_STDIO_SIZE, stdin);char *buf = stdio_buf;n = read_int(buf);m = read_int(buf);for (unsigned int i = 0; i < n; i++) {a[i] = read_int(buf);}for (unsigned int i = 0; i < m; i++) {b[i] = read_int(buf);}}void write_int(char *&buf, std::uint32_t x) {constexpr std::uint32_t eight_digit = 100000000;if (x >= eight_digit) [[likely]] {std::uint32_t upper = x / eight_digit, lower = x % eight_digit;*buf = '0' + upper;buf++;*reinterpret_cast<std::uint64_t *>(buf) = int_to_char_arr(lower) + 0x3030303030303030ull;buf += 8;} else {std::uint64_t char_arr = int_to_char_arr(x);unsigned int padding = __builtin_ctzll(char_arr + (1ull << 63)) >> 3, len = 8 - padding;char_arr += 0x3030303030303030ull;*reinterpret_cast<std::uint64_t *>(buf) = char_arr >> (padding << 3);buf += len;}*buf = ' ';buf++;}void write(unsigned int n, std::uint32_t *a) {char *buf = stdio_buf;for (unsigned int i = 0; i < n; i++) {write_int(buf, a[i]);}unsigned int len = buf - stdio_buf;std::fwrite(stdio_buf, 1, len, stdout);}} io;alignas(32) static std::uint32_t v1[MAX_N * 2], v2[MAX_N * 2];template<int M, int K, int G> struct Fft {// 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...int g[1 << (K - 1)];constexpr Fft() : g() { //if tl constexpr...static_assert(K >= 2, "Fft: K >= 2 must hold");g[0] = 1;g[1 << (K - 2)] = G;for (int l = 1 << (K - 2); l >= 2; l >>= 1) {g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;}assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);for (int l = 2; l <= 1 << (K - 2); l <<= 1) {for (int i = 1; i < l; ++i) {g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;}}}void fft(vector<int> &x) const {const int n = x.size();assert(!(n & (n - 1)) && n <= 1 << K);for (int h = __builtin_ctz(n); h--; ) {const int l = 1 << h;for (int i = 0; i < n >> 1 >> h; ++i) {for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;if ((x[j] += t) >= M) x[j] -= M;}}}for (int i = 0, j = 0; i < n; ++i) {if (i < j) std::swap(x[i], x[j]);for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}}}vector<int> convolution(const vector<int> &a, const vector<int> &b) const {if(a.empty() || b.empty()) return {};const int na = a.size(), nb = b.size();int n, invN = 1;for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;vector<int> x(n, 0), y(n, 0);std::copy(a.begin(), a.end(), x.begin());std::copy(b.begin(), b.end(), y.begin());fft(x);fft(y);for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;std::reverse(x.begin() + 1, x.end());fft(x);x.resize(na + nb - 1);return x;}};Fft<998244353,23,31> muls;vector<int> operator *(vector<int> v1,vector<int> v2){return muls.convolution(v1,v2);}int32_t main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);/*string s="abbaaaf";vector<int> sa=suffix_array(s,256);vector<int> lc=build_lcp(s,sa);for(int i:sa) cout<<i<<' '; cout<<endl;for(int i:lc) cout<<i<<' '; cout<<endl;*/int t;cin>>t;while(t--){int n,m;cin>>n>>m;string s1,s2;cin>>s1>>s2;string s0=s1;bool ok[n-m+1];for(int i=0;i<=n-m;++i) ok[i]=true;int h=1;while(h<=n+m) h*=2;for(char c='a';c<='z';++c){int cnt=0;for(int i=0;i<h;++i) {v1[i]=0;v2[i]=0;}for(int i=0;i<n;++i) v1[n-i-1]=(s1[i]==c || s1[i]=='?');for(int i=0;i<m;++i) {v2[i]=(s2[i]==c);cnt+=v2[i];}if(h>=2000) convolution(h, v1, v2);else{vector<int> v11;for(int i=0;i<n;++i) v11.push_back(v1[i]);vector<int> v21;for(int i=0;i<m;++i) v21.push_back(v2[i]);vector<int> v31=v11*v21;for(int i=m-1;i<=n-1;++i) v1[i]=v31[i];}for(int i=m-1;i<=n-1;++i){ok[n-i-1]&=(v1[i]==cnt);}}for(int i=0;i<s1.size();++i) if(s1[i]=='?') s1[i]='a';string s=s1;s.push_back('$');s+=s2;if(accumulate(ok,ok+n-m+1,0LL)==0){cout<<(-1)<<'\n';continue;}vector<int> sa=suffix_array(s,256);vector<int> lc=build_lcp(s,sa);vector<int> pos(s.size());for(int i=0;i<s.size();++i){pos[sa[i]]=i;}int lcsz=lc.size();for(int i=0;i<lcsz;++i){sp[i][0]=lc[i];}for(int j=1;j<20;++j){for(int i=0;i<=lcsz-(1<<j);++i){sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);}}int l1=0;int l2=s1.size()+1;int inf=1e9;/*string stupid;{for(int i=0;i<=n-m;++i) if(ok[i]){string ans=s1.substr(0,i);ans+=s2;ans+=s1.substr(i+m,n-m-i);if(stupid.empty()) stupid=ans;else stupid=min(stupid,ans);}}*/auto get=[&](int i,int j){int i1=i;int j1=j;i=pos[i];j=pos[j];if(i>j) swap(i,j);if(i==j) return inf;int o=31-__builtin_clz(j-i);return min(sp[i][o],sp[j-(1<<o)][o]);};auto cmp=[&](int i,int j)->bool{if(i==j) return false;bool sw=false;if(i>j) {swap(i,j);sw=true;}{if(j-i<s2.size()){int pos1=get(i,l2);if(pos1<j-i){return (s[l2+pos1]<s[i+pos1])^sw;}int pos2=get(l2,l2+j-i);if(pos2<m-(j-i)){return (s[l2+j-i+pos2]<s[l2+pos2])^sw;}int pos3=get(i+m,l2+m-(j-i));if(pos3<(j-i)){return (s[i+m+pos3]<s[l2+m-(j-i)+pos3])^sw;}return false;}else{int pos1=get(i,l2);if(pos1<m){return (s[l2+pos1]<s[i+pos1])^sw;}int pos2=get(j,l2);if(pos1<m){return (s[j+pos1]<s[l2+pos1])^sw;}return false;}}};vector<int> v;for(int i=0;i<=n-m;++i) if(ok[i]) v.push_back(i);int pos1=(*min_element(v.begin(),v.end(),cmp));string ans=s1.substr(0,pos1);ans+=s2;ans+=s1.substr(pos1+m,n-m-pos1);/*if(ans!=stupid){cout<<s0<<' '<<s1<<' '<<s2<<endl;cout<<ans<<' '<<stupid<<endl;}assert(ans==stupid);*/cout<<ans<<'\n';}return 0;}/*112 3t?t?r???g?s?kog*/