Submission #922717

#	Time	Username	Problem	Language	Result	Execution time	Memory
922717		boyliguanhan	Palinilap (COI16_palinilap)	C++17	100 / 100	187 ms	25176 KiB

palinilap

#include<bits/stdc++.h>
#define N 100100
using namespace std;
#define X (1<<j)
long long ans,nc,cont[N][26],bad[2][N],n,hl[N],hr[N],pw[N]{1},A=31,B=1e9+7;
int Hl(int l, int r) {return(hl[r]-hl[l]*pw[r-l]%B+B)%B;}
int Hr(int l, int r) {return(hr[l]-hr[r]*pw[r-l]%B+B)%B;}
int main() {
    for(int i=1;i<N;i++) pw[i]=pw[i-1]*A%B;
    string str;
    char c=getchar();
    while(c>'A')str+=c,c=getchar();
    n=str.size();
    for(int i=1;i<=n;i++)
        hl[i]=hr[i]=str[i-1]-'a'+1;
    for(int i=1;i<n;i++)
        hl[i+1]+=(hl[i]*A)%B,
        hr[n-i]+=(hr[n-i+1]*A)%B;
    for(int i=1;i<n;i++){
        int p1=i,p2=i+1,p3,p4;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        bad[1][p2-1]++,bad[1][i]+=i-p2,bad[1][i-1]+=p2-i-1;
        nc+=i-p1;
        bad[0][p1+1]++;bad[0][i+1]+=p1-i-1;bad[0][i+2]+=i-p1;
        p3=p1--,p4=p2++;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
            cont[p4][str[p3-1]-'a']+=p3-p1;
    }
    for(int i=1;i<=n;i++){
        int p1=i,p2=i,p3,p4;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        bad[1][p2-1]++,bad[1][i]+=p1-i,bad[1][i-1]+=i-p1-1;
        nc+=i-p1;
        bad[0][p1+1]++,bad[0][i]+=p1-i;bad[0][i+1]+=i-p1-1;
        p3=p1--,p4=p2++;
        for(int j = (int)log2(n)+1; j--;)
            if(p1>=X&&p2+X<n+2&&Hl(p1-X,p1)==Hr(p2,p2+X))
                p1-=X,p2+=X;
        if(p3&&p4<=n)cont[p3][str[p4-1]-'a']+=p3-p1,
            cont[p4][str[p3-1]-'a']+=p3-p1;
    }
    for(int i=2;i<=n;i++)
        bad[0][i]+=bad[0][i-1];
    for(int i=2;i<=n;i++)
        bad[0][i]+=bad[0][i-1];
    for(int i=n;--i;)
        bad[1][i]+=bad[1][i+1];
    for(int i=n;--i;)
        bad[1][i]+=bad[1][i+1];
    for(int i=1;i<=n;i++)for(auto j:cont[i])
        ans=max(ans,j-bad[0][i]-bad[1][i]);
    cout<<ans+nc;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46