제출 #531524

#제출 시각아이디문제언어결과실행 시간메모리
531524RegisterPalinilap (COI16_palinilap)C++14
54 / 100
44 ms26304 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=1e5+5,S=26,b=233; int n; ull p[N],h[N],rh[N]; ll sum,ans,f[N][S],d1[N],dd1[N],d2[N],dd2[N]; char c[N]; ull val(int l,int r) {return h[r]-h[l-1]*p[r-l+1];} ull rval(int l,int r) {return rh[l]-rh[r+1]*p[r-l+1];} int main(){ scanf("%s",c+1);n=strlen(c+1);p[0]=1; for(int i=1;i<=n;i++) p[i]=p[i-1]*b,h[i]=h[i-1]*b+c[i]; for(int i=n;i;i--) rh[i]=rh[i+1]*b+c[i]; for(int i=1;i<=n;i++){ int l=2,r=min(i,n-i+1),s=1; while(l<=r){ int mid=l+r>>1; if(rval(i-mid+1,i)==val(i,i+mid-1)) s=mid,l=mid+1; else r=mid-1; } d1[i-s+1]++;d1[i]--;dd1[i]-=s-1; d2[i+s-1]++;d2[i]--;dd2[i]-=s-1; sum+=s; if(i-s>0&&i+s<=n){ int v=1;l=2;r=min(i-s,n-i-s+1); while(l<=r){ int mid=l+r>>1; if(rval(i-s-mid+1,i-s-1)==val(i+s+1,i+s+mid-1)) v=mid,l=mid+1; else r=mid-1; } f[i-s][c[i+s]-'a']+=v; f[i+s][c[i-s]-'a']+=v; } } for(int i=1;i<n;i++){ int l=1,r=min(i,n-i),s=0; while(l<=r){ int mid=l+r>>1; if(rval(i-mid+1,i)==val(i+1,i+mid)) s=mid,l=mid+1; else r=mid-1; } d1[i-s+1]++;d1[i+1]--;dd1[i+1]-=s; d2[i+s]++;d2[i]--;dd2[i]-=s; sum+=s; if(i-s>0&&i+1+s<=n){ int v=1;l=2;r=min(i-s,n-i-s); while(l<=r){ int mid=l+r>>1; if(rval(i-s-mid+1,i-s-1)==val(i+s+2,i+s+mid)) v=mid,l=mid+1; else r=mid-1; } f[i-s][c[i+1+s]-'a']+=v; f[i+1+s][c[i-s]-'a']+=v; } } for(int t=0;t<2;t++) for(int i=1;i<=n;i++) d1[i]+=d1[i-1]+(t?dd1[i]:0); for(int t=0;t<2;t++) for(int i=n;i;i--) d2[i]+=d2[i+1]+(t?dd2[i]:0); ans=sum; for(int i=1;i<=n;i++) for(int j=0;j<S;j++) if(c[i]!='a'+j) ans=max(ans,sum-d1[i]-d2[i]+f[i][j]); printf("%lld\n",ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

palinilap.cpp: In function 'int main()':
palinilap.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |    int mid=l+r>>1;
      |            ~^~
palinilap.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=l+r>>1;
      |             ~^~
palinilap.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |    int mid=l+r>>1;
      |            ~^~
palinilap.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid=l+r>>1;
      |             ~^~
palinilap.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%s",c+1);n=strlen(c+1);p[0]=1;
      |  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...