Submission #388119

#	Time	Username	Problem	Language	Result	Execution time	Memory
388119		leaked	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	260 ms	65540 KiB

necklace

#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;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it   = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
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);
    {
        /// заканчивая в j and staring at i
        for(int i=0;i<n;i++){
            string 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++){
            string 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++){
            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-(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

*/

• Subtask 1: 0 / 15