Submission #1165820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165820		sitablechair	Necklace (Subtask 4) (BOI19_necklace4)	C++20	3 / 15	384 ms	520 KiB

necklace

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=3003;

string s,s1,s2,s3;
int pf[N*2],pf1[N*2];

pair<int,pair<int,int>> solve() {
    int ans=0,x1=-1,y1=-1;
    int n=sz(s)-1,m=sz(s1)-1;
    For(i,1,m-1) {
        s2=s3=" ";
        ForD(j,i,1) s2+=s1[j];
        s2+="%";
        ForD(j,n,1) s2+=s[j];
        For(j,i+1,m) s3+=s1[j];
        s3+="%";
        For(j,1,n) s3+=s[j];
        int p=sz(s2)-1,q=sz(s3)-1;
        fill(pf,pf+1+p,0);
        fill(pf1,pf1+1+q,0);
        For(j,2,p) {
            int k=pf[j-1];
            while(true) {
                if (s2[k+1]==s2[j]) {
                    pf[j]=k+1;
                    break;
                }
                if (k==0) break;
                k=pf[k];
            }
        }
        For(j,2,p) {
            int k=pf1[j-1];
            while(true) {
                if (s3[k+1]==s3[j]) {
                    pf1[j]=k+1;
                    break;
                }
                if (k==0) break;
                k=pf1[k];
            }
        }
        For(j,2,n) {
            int x=pf[n-j+i+2];
            if (x>n-j+1) x=n-j+1;
            if (x>i) x=i;
            int y=pf1[m-i+j];
            if (y>m-i) y=m-i;
            if (y>j-1) y=j-1;
            if (x+y>ans) {
                ans=x+y;
                y1=i-x+1;
                x1=j-y;
            }
        }
    }
    if (m==1) {
        For(j,1,n) 
            if (s[j]==s1[1]) return {1,{j,1}};
    }
    if (n==1) {
        For(j,1,m)
            if (s1[j]==s[1]) return {1,{1,j}};
    }
    // debug(ans,x1,y1);
    return {ans,{x1,y1}};
} 

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> s >> s1;
    s=" "+s;
    s1=" "+s1;
    auto xx=solve();
    reverse(all(s));
    s.pop_back();
    s=" "+s;
    auto xxx=solve();
    // pair<int,pair<int,int>> xxx={-1,{0,0}};
    int tmp=sz(s)-1;
    xxx.ss.ff=tmp-xxx.ss.ff+1;
    // cout << max(xxx.ff,xx.ff) << endl;
    if (xxx.ff>xx.ff) cout << xxx.ff << endl << xxx.ss.ff-xxx.ff << " " << xxx.ss.ss-1 << endl;
    else cout << xx.ff << endl << xx.ss.ff-1 << " " << xx.ss.ss-1 << endl;
    return 0;
}

• Subtask 1: 3 / 15