oj.uz

Submission #657143

# Submission time Handle Problem Language Result Execution time Memory
657143 2022-11-08T22:59:30 Z inksamurai Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 307 ms 572 KB 
#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;
	// s=string(3000,'a');
	string t;
	// t=string(3000,'a');
	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];
					// cout<<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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 368 KB Output is correct
7 Correct 5 ms 372 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 6 ms 372 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 372 KB Output is correct
12 Correct 6 ms 360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 368 KB Output is correct
7 Correct 5 ms 372 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 6 ms 372 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 372 KB Output is correct
12 Correct 6 ms 360 KB Output is correct
13 Correct 300 ms 456 KB Output is correct
14 Correct 269 ms 464 KB Output is correct
15 Correct 307 ms 468 KB Output is correct
16 Correct 291 ms 468 KB Output is correct
17 Correct 234 ms 572 KB Output is correct
18 Correct 245 ms 460 KB Output is correct
19 Correct 259 ms 464 KB Output is correct
20 Correct 275 ms 440 KB Output is correct
21 Correct 287 ms 464 KB Output is correct