oj.uz

Submission #882091

# Submission time Handle Problem Language Result Execution time Memory
882091 2023-12-02T15:12:18 Z DucNguyen2007 Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 147 ms 2652 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxN=1e6+5;
#define ll long long
#define ben(x) x.begin(),x.end()
string s,t;
ll ans[3],n,m,p1[maxN+1],p2[maxN+1];
void calc(string s,ll p[])
{
    ll n=s.length();
    p[0]=0;
    for(int i=1;i<n;i++)
    {

        ll j=p[i-1];
        while(j>0&&s[i]!=s[j])
        {
            j=p[j-1];
        }
        if(s[i]==s[j])
        {
            j++;
        }
        p[i]=j;
    }
}
void solve(string s,string t,bool rev)
{
    string t_rev=t;
    reverse(ben(t_rev));
    for(int i=0;i<n;i++)
    {
        string l=s.substr(0,i),r=s.substr(i,n);
        reverse(ben(l));
        string a=l+"#"+t;
        string b=r+"#"+t_rev;
        calc(a,p1);
        calc(b,p2);
        for(int j=1;j<=m;j++)
        {
            ll cur1=p1[i+j];
            ll cur2=p2[n+m-j-i];
            if(cur1+cur2>ans[0])
            {
                ans[0]=cur1+cur2;
                ans[1]=i-p1[i+j];
                if(rev)
                {
                    ans[2]=m-j-cur2;
                }
                else ans[2]=j-cur1;
            }
        }
    }
}
int main()
{
    cin>>s>>t;
    n=s.length(),m=t.length();
    solve(s,t,0);
    reverse(ben(t));
    solve(s,t,1);
    cout<<ans[0]<<'\n'<<ans[1]<<" "<<ans[2];
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2640 KB Output is correct
2 Correct 114 ms 2652 KB Output is correct
3 Correct 136 ms 2624 KB Output is correct
4 Correct 115 ms 2396 KB Output is correct
5 Correct 98 ms 2628 KB Output is correct
6 Correct 116 ms 2652 KB Output is correct
7 Correct 107 ms 2396 KB Output is correct
8 Correct 117 ms 2392 KB Output is correct
9 Correct 118 ms 2396 KB Output is correct