Submission #657117

#	Time	Username	Problem	Language	Result	Execution time	Memory
657117		inksamurai	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1586 ms	548 KiB

necklace

#include <bits/stdc++.h>

// cut here
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
 
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
 
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
 
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
 
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
 
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
 
    S all_prod() { return d[1]; }
 
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
 
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
 
  private:
    int _n, size, log;
    std::vector<S> d;
 
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
 
}  // namespace atcoder
// cut here 

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;
}

pii op(pii l,pii r){return l.fi>r.fi?l:r;}
pii e(){return {0,-1};}

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;
				vi pfb(sz(cur),0);
				if(sz(cur)<1000){
					pfb=eval_pf1(cur);
				}
				rng(j,i+1,sz(cur)){
					b[j-(i+1)]=pfb[j];
				}
			}
			atcoder::segtree<pii,op,e> seg(m+1);
			rep(i,m+1){
				if(i==m){
					seg.set(i,{m,i});
				}else{
					seg.set(i,{a[i]+i,i});
				}
			}
			rep(j,m){
				if(s[i]==t[j]){
					if(j+1<m){
						int frm=j+1;
						int to=frm+b[frm]-1;
						pii q=seg.prod(frm,to+2);
						int now=q.fi-frm+1;
						if(now>len){
							len=now;
							int ni=i-(q.se-frm);
							p={ni,j};
							if(_==1){
								p={n-ni-now,j};
							}
						}
					}
					{
						int now=1;
						if(now>len){
							len=now;
							int ni=i;
							p={ni,j};
							if(_==1){
								p={n-ni-now,j};
							}
						}
					}
				}
			}		
		}
		reverse(all(s));
	}
	cout<<len<<"\n";
	cout<<p.fi<<" "<<p.se<<"\n";
}

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