Submission #29786

#	Time	Username	Problem	Language	Result	Execution time	Memory
29786		TAMREF	Palinilap (COI16_palinilap)	C++11	17 / 100	1000 ms	2232 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
const int mx=5005;
char a[mx],S[mx<<1];
int dp[mx<<1], Z, r,p,np;
void input(){
    ios_base::sync_with_stdio(false);
    scanf("%s",a);
    int N=strlen(a);
    int i=0;
    for(int k=0;k<N;k++){
        S[++i]=a[k];
        S[++i]='*';
    }
    Z=2*N-1;
}
int Manacher(int t, char c){
    r=p=np=0; //p=np
    char x=S[t];
    S[t]=c;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=Z;i++){
        dp[i]=(i>r)?0:min(dp[2*p-i],r-i);
        for(;i+dp[i]+1<=Z && S[i+dp[i]+1]==S[i-dp[i]-1];++dp[i]);
        if(i+dp[i]>r) p=i,r=i+dp[i];
        if(!dp[i]) np+=(S[i]=='*'?0:1);
        else if(dp[i]==i-1||dp[i]+i==Z) np+=(S[i]=='*'?(dp[i]+1)>>1:(dp[i]+2)>>1);
        else np+=(S[i]=='*'?(dp[i]>>1):(dp[i]+1)>>1);
    }
    S[t]=x;
    return np;
}
int main(){
    input();
    int X=0;
    for(int i=1;i<=Z;i+=2){
        for(char x='a';x<='z';x++){
            /*
            if(X<Manacher(i,x)){
                swap(S[i],x);
                puts(S+1);
                swap(S[i],x);
                for(int i=1;i<=Z;i++) printf("%d",dp[i]);
                puts("");
            }*/
            X=max(X,Manacher(i,x));
        }
    }
    printf("%d\n",X);
}

Compilation message (stderr)

palinilap.cpp: In function 'void input()':
palinilap.cpp:8:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",a);
                  ^

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