oj.uz

Submission #29786

# Submission time Handle Problem Language Result Execution time Memory
29786 2017-07-20T16:11:11 Z TAMREF Palinilap (COI16_palinilap) C++11
17 / 100
 1000 ms 2232 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2232 KB Output is correct
2 Correct 6 ms 2232 KB Output is correct
3 Correct 6 ms 2232 KB Output is correct
4 Correct 6 ms 2232 KB Output is correct
5 Correct 6 ms 2232 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2232 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -