結果

問題 No.2231 Surprising Flash!
ユーザー maksimmaksim
提出日時 2023-02-24 22:36:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,677 bytes
コンパイル時間 8,232 ms
コンパイル使用メモリ 405,156 KB
実行使用メモリ 75,360 KB
最終ジャッジ日時 2023-10-11 08:40:08
合計ジャッジ時間 95,174 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
22,020 KB
testcase_01 AC 16 ms
21,852 KB
testcase_02 AC 221 ms
21,928 KB
testcase_03 AC 628 ms
21,840 KB
testcase_04 AC 119 ms
22,000 KB
testcase_05 AC 161 ms
22,040 KB
testcase_06 AC 215 ms
22,008 KB
testcase_07 AC 17 ms
21,876 KB
testcase_08 AC 55 ms
21,856 KB
testcase_09 AC 14 ms
21,904 KB
testcase_10 AC 57 ms
22,056 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 AC 3,715 ms
24,676 KB
testcase_17 AC 3,928 ms
27,840 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 AC 1,794 ms
23,368 KB
testcase_40 AC 1,156 ms
23,392 KB
testcase_41 AC 14 ms
21,988 KB
testcase_42 AC 15 ms
21,772 KB
testcase_43 AC 14 ms
21,952 KB
testcase_44 AC 259 ms
21,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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
*/
0