Submission #1238330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238330		Unforgettablepl	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	29 / 85	1593 ms	584 KiB

necklace

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

__int128 a = 2514364;
__int128 m = (1ll<<61)-1;

__int128 powers[3001];

struct hashedString{
    string baseStr;
    vector<__int128> Phash;
    void init(){
        Phash.resize(baseStr.size());
        __int128 curr = 0;
        for(int i=0;i<baseStr.size();i++){
            curr=curr*a + (baseStr[i]-'a'+1);
            curr%=m;
            Phash[i]=curr;
        }
    }
    __int128 getHash(int i,int j){
        __int128 hashI = 0;
        if(i)hashI = Phash[i-1];
        return (Phash[j]-(hashI*powers[j-i+1])%m + m)%m;
    }
    int size(){
        return baseStr.size();
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    powers[0]=1;
    for(int i=1;i<=3000;i++)powers[i]=(powers[i-1]*a)%m;
    hashedString p,q,qq;
    cin >> p.baseStr >> q.baseStr;
    qq.baseStr = q.baseStr;
    reverse(qq.baseStr.begin(),qq.baseStr.end());
    p.init();q.init();qq.init();
    tuple<int,int,int> ans = {0,0,0};
    // loop over str8
    vector<pair<int,int>> Rd(p.size());
    for(int i=0;i<q.size();i++){
        for(int j=0;j<p.size();j++){
            int R = j+1;
            for(int jump=(1<<11);jump;jump/=2){
                if(R-jump<0)continue;
                if(i-(j-R+jump+1)<0)continue;
                if(p.getHash(R-jump,j)==q.getHash(i-(j-R+jump+1),i-1))R-=jump;
            }
            Rd[j]={R-1,j};
        }
        sort(Rd.begin(),Rd.end());
        for(int j=0;j<p.size();j++){
            int L = j-1;
            for(int jump=(1<<11);jump;jump/=2){
                if(L+jump>=p.size())continue;
                if(i+L+jump-j>=q.size())continue;
                if(p.getHash(j,L+jump)==q.getHash(i,i+L+jump-j))L+=jump;
            }
            auto iter = upper_bound(Rd.begin(),Rd.end(),make_pair(L,5000ll));
            if(iter!=Rd.begin()){
                iter--;
                ans=max(ans,{iter->second-j+1,j,L+i-iter->second});
            }
        }
    }
    // loop over reverse
    for(int i=0;i<qq.size();i++){
        vector<pair<int,int>> Rd(p.size());
        for(int j=0;j<p.size();j++){
            int R = j+1;
            for(int jump=(1<<11);jump;jump/=2){
                if(R-jump<0)continue;
                if(i-(j-R+jump+1)<0)continue;
                if(p.getHash(R-jump,j)==qq.getHash(i-(j-R+jump+1),i-1))R-=jump;
            }
            Rd[j]={R-1,j};
        }
        sort(Rd.begin(),Rd.end());
        for(int j=0;j<p.size();j++){
            int L = j-1;
            for(int jump=(1<<11);jump;jump/=2){
                if(L+jump>=p.size())continue;
                if(i+L+jump-j>=qq.size())continue;
                if(p.getHash(j,L+jump)==qq.getHash(i,i+L+jump-j))L+=jump;
            }
            auto iter = upper_bound(Rd.begin(),Rd.end(),make_pair(L,5000ll));
            if(iter!=Rd.begin()){
                iter--;
                ans=max(ans,{iter->second-j+1,j,qq.size()-1-(L+i-j)});
            }
        }
    }
    cout << get<0>(ans) << '\n' << get<1>(ans) << ' ' << get<2>(ans) << '\n';
}

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