結果
| 問題 |
No.2231 Surprising Flash!
|
| コンテスト | |
| ユーザー |
 maksim
|
| 提出日時 | 2023-02-24 22:36:55 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,677 bytes |
| コンパイル時間 | 8,491 ms |
| コンパイル使用メモリ | 408,516 KB |
| 実行使用メモリ | 75,112 KB |
| 最終ジャッジ日時 | 2024-09-13 07:54:51 |
| 合計ジャッジ時間 | 136,278 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 16 TLE * 28 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+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);}
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;
for(char c='a';c<='z';++c)
{
vector<int> v1(n),v2(m);
int cnt=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];}
vector<int> h=v1*v2;
for(int i=m-1;i<=n-1;++i)
{
ok[n-i-1]&=(h[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;
}
/*
1
12 3
t?t?r???g?s?
kog
*/