Submission #388126

#TimeUsernameProblemLanguageResultExecution timeMemory
388126leakedNecklace (Subtask 1-3) (BOI19_necklace1)C++14
85 / 85
654 ms71036 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define m_p make_pair
#define vec vector
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker,"/stack:20000000")
//#pragma GCC target("sse,sse2,sse3,sse3,ssse3,abm,avx,avx2,tune=native")
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> bool umax(T &a, T b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a, T b){return (a>b?a=b,1:0);}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef unsigned long long ull;
const int N=3e3+2;
int dp1[N][N];
int dp2[N][N];
int func[2*N];
void calc(int *pf,const string &s){
    for(int i=1;i<sz(s);i++){
        int j=pf[i-1];
        while(j>0 && s[j]!=s[i]){
            j=pf[j-1];
        }
        pf[i]=j;
        pf[i]+=(s[i]==s[j]);
    }
}
signed main(){
    fast_ioi;
    string s,t;
    cin>>s>>t;
    int ans=-1;
    int f=-1,se=-1;
    int n=sz(s),m=sz(t);
    string lel;
    {
        /// заканчивая в j and staring at i
        for(int i=0;i<n;i++){
            lel=s.substr(i,n-1)+'#'+t;
            int w=(n-1-i+1)+1;
            calc(func,lel);
            for(int j=0;j<m;j++){
                dp1[i][j]=func[j+w];
            }
        }
        /// заканчивая в i and staring at j
        for(int j=0;j<m;j++){
            lel=t.substr(j,m-1)+'#'+s;
            int w=(m-1-j+1)+1;
            calc(func,lel);
            for(int i=0;i<n;i++){
                dp2[i][j]=func[i+w];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int st1=i-(i?dp2[i-1][j]:0),st2=j-(j?dp1[i][j-1]:0);
                int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
                if(umax(ans,dl)){
                    f=st1,se=st2;
                }
            }
        }
    }
//    {
//        reverse(all(s));
//        /// заканчивая в j and staring at i
//        for(int i=0;i<n;i++){
//            string lel=s.substr(i,n-1)+'#'+t;
//            int w=(n-i)+1;
//            calc(func,lel);
//            for(int j=0;j<m;j++){
//                dp1[i][j]=func[j+w];
//            }
//        }
//        /// заканчивая в i and staring at j
//        for(int j=0;j<m;j++){
//            string lel=t.substr(j,m-1)+'#'+s;
//            int w=(m-j)+1;
//            calc(func,lel);
//            for(int i=0;i<n;i++){
//                dp2[i][j]=func[i+w];
//            }
//        }
//        for(int i=0;i<n;i++){
//            for(int j=0;j<m;j++){
//                int st1=i+(j?dp1[i][j-1]-1:0),st2=j-(j?dp1[i][j-1]:0);
//                int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
////                st1=n-st1-1;
//                if(umax(ans,dl)){
//                    f=st1,se=st2;
//
//                }
////                debug()<<imie(s)imie(t)imie(i)imie(j)imie(dp1[i][j])imie(dp2[i][j]);
////                print(i);print(j);print()
//            }
//        }
//        reverse(all(s));
//    }
//
    {
        reverse(all(t));
        /// заканчивая в j and staring at i
        for(int i=0;i<n;i++){
            lel=s.substr(i,n-1)+'#'+t;
            int w=(n-i)+1;
            calc(func,lel);
            for(int j=0;j<m;j++){
                dp1[i][j]=func[j+w];
            }
        }
        /// заканчивая в i and staring at j
        for(int j=0;j<m;j++){
            lel=t.substr(j,m-1)+'#'+s;
            int w=(m-j)+1;
            calc(func,lel);
            for(int i=0;i<n;i++){
                dp2[i][j]=func[i+w];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int st1=i-(i?dp2[i-1][j]:0),st2=j+(i?dp2[i-1][j]-1:0);
                int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
                st2=m-st2-1;
                if(umax(ans,dl)){
                    f=st1,se=st2;
//                    debug()<<imie(j)imie(s)imie(t)imie(i?dp2[i-1][j]:0)imie((j?dp1[i][j-1]:0));
                }
            }
        }
        reverse(all(t));
    }
    assert(ans!=-1);
    cout<<ans<<endl<<f<<' '<<se;
    return 0;
}
/*

zxyabcd
ztcdabxy
yxbadctz

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...