Submission #657109

#	Time	Username	Problem	Language	Result	Execution time	Memory
657109		inksamurai	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	3 ms	340 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3NRqilq ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

// include mint here
using hshmint=modint<1000000007>;
using hshmint1=modint<998244353>;
using magicpair=pair<hshmint,hshmint1>;
struct rollhsh{	
	hshmint _p=9973; // base
	hshmint1 _p1=257; // base1
	vec(hshmint) pw,invpw;
	vec(hshmint1) pw1,invpw1;
	vec(magicpair) hsh;
	rollhsh(string s=""){
		init(s);
	}
	void init(string s){
		// put this out in global if multiple testcases
		hsh.clear();
		pw.clear();
		invpw.clear();
		pw1.clear();
		invpw1.clear();
		hsh.resize(sz(s)+1);
		pw.resize(sz(s)+1);
		invpw.resize(sz(s)+1);
		pw1.resize(sz(s)+1);
		invpw1.resize(sz(s)+1);
		hsh[0]={1,1};
		pw[0]=1;
		pw1[0]=1;
		invpw[0]=1;
		invpw1[0]=1;		
		hshmint _invbase=_p.x;
		hshmint1 _invbase1=_p1.x;
		_invbase=_invbase.inv(); _invbase1=_invbase1.inv();
		rep(i,sz(s)){
			pw[i+1]=pw[i]*_p;
			pw1[i+1]=pw1[i]*_p1;
			invpw[i+1]=invpw[i]*_invbase;
			invpw1[i+1]=invpw1[i]*_invbase1;
			hshmint x=(int)(s[i]-'a'+1);
			hshmint1 x1=(int)(s[i]-'a'+1);
			hsh[i+1]={hsh[i].fi+pw[i]*x,hsh[i].se+pw1[i]*x1};
		}
	}
	pair<ll,ll> get(int l,int r){ 
		// from - to , inclusive
		hshmint _f=invpw[l]*(hsh[r+1].fi-hsh[l].fi);
		hshmint1 _s=invpw1[l]*(hsh[r+1].se-hsh[l].se);
		return {_f.x,_s.x};	
	}
};

#define all(a) a.begin(),a.end()

vi eval_pf(string s){
	int n=sz(s);
	vi pf(n);
	rng(i,1,n){
		int j=pf[i-1];
		while(j and s[i]!=s[j]){
			j=pf[j-1];
		}
		j+=(s[i]==s[j]);
		pf[i]=j;
	}
	return pf;
}

vi eval_pf1(string s){
	int n=sz(s);
	rollhsh hsh(s); // please don't tle
	vi pf(n);
	int frm=-1;
	rep(i,n){
		if(s[i]=='.'){
			frm=i;
		}
	}
	frm++;
	rng(i,frm,n){
		int l=1,r=n-i;
		int c=0;
		while(l<=r){
			int m=(l+r)/2;
			if(hsh.get(0,m-1)==hsh.get(i,i+m-1)){
				c=m,l=m+1;
			}else{
				r=m-1;
			}
		}
		pf[i]=c;
	}
	return pf;
}

signed main(){
_3NRqilq;	
	string s;
	cin>>s;
	string t;
	cin>>t;
	string rt=t;
	reverse(all(rt));
	int n=sz(s);
	int m=sz(t);
	int len=0;
	pii p={0,0};
	rep(_,2){
		rep(i,n)
		{
			vi a(m);
			if(i<n-1){
				string cur=s.substr(i+1,n-i-1);
				cur+=".";
				cur+=rt;
				auto pfa=eval_pf(cur);
				rng(j,n-i,sz(cur)){
					a[m-(j-(n-i))-1]=pfa[j];
				}
			}
			vi b(m);
			if(i){
				string cur="";
				cur+=s.substr(0,i);
				reverse(all(cur));
				cur+=".";
				cur+=t;
				auto pfb=eval_pf1(cur);
				rng(j,i+1,sz(cur)){
					b[j-(i+1)]=pfb[j];
				}
			}
			rep(j,m){
				if(s[i]==t[j]){
					if(j+1<m){
						int frm=j+1;
						int to=frm+b[frm]-1;
						rng(k,frm,to+1){
							int now=k-frm+1+(k+1<m?a[k+1]:0)+1;
							if(now>len){
								len=now;
								// print(frm-k);
								int ni=i-(k-frm)-1;
								p={ni,j};
								if(_==1){
									p={n-ni-1,j};
								}
							}
						}
					}
					{
						int now=1;
						if(now>len){
							len=now;
							int ni=i;
							p={ni,j};
							if(_==1){
								p={n-ni-1,j};
							}
						}
					}
				}
			}		
		}
		reverse(all(s));
	}
	cout<<len<<"\n";
	cout<<p.fi<<" "<<p.se<<"\n";
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40