Submission #657144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
657144	2022-11-08T23:00:11 Z	inksamurai	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	338 ms	576 KB

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

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

vi eval_pf(const 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;
}

// cp algorithms Z-function and its calculation
vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

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};
	vi a(m),b(m);
	vec(pii) dp(m+1);
	rep(_,2){
		rep(i,n)
		{
			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];
				}
			}
			if(i){
				string cur="";
				cur+=s.substr(0,i);
				reverse(all(cur));
				cur+=".";
				cur+=t;
				auto pfb=z_function(cur);
				rng(j,i+1,sz(cur)){
					b[j-(i+1)]=pfb[j];
				}
			}
			rep(j,m+1){
				dp[j]=pii(j==m?m:(j+a[j]),j);
				if(j){
					dp[j]=max(dp[j],dp[j-1]);
				}
			}
			rep(j,m){
				if(s[i]==t[j]){
					if(j+1<m){
						int frm=j+1;
						int to=frm+b[frm]-1;
						pii q=dp[to+1];
						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

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	310 ms	480 KB	Output is correct
2	Correct	278 ms	472 KB	Output is correct
3	Correct	338 ms	456 KB	Output is correct
4	Correct	257 ms	428 KB	Output is correct
5	Correct	220 ms	472 KB	Output is correct
6	Correct	259 ms	556 KB	Output is correct
7	Correct	263 ms	432 KB	Output is correct
8	Correct	284 ms	576 KB	Output is correct
9	Correct	284 ms	460 KB	Output is correct