제출 #531536

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
531536	2022-03-01 02:46:35	Register	Palinilap (COI16_palinilap)	C++14	100 / 100	92 ms	27592 KiB

palinilap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,S=26,b=229,bi=233,mod=1e9+7;
int n;
ull p[N],h[N],rh[N];
int pi[N],hi[N],rhi[N];
ll sum,ans,f[N][S],d1[N],dd1[N],d2[N],dd2[N];
char c[N];
pair<ull,int> val(int l,int r) {return make_pair(h[r]-h[l-1]*p[r-l+1],(hi[r]+mod-1ll*hi[l-1]*pi[r-l+1]%mod)%mod);}
pair<ull,int> rval(int l,int r) {return make_pair(rh[l]-rh[r+1]*p[r-l+1],(rhi[l]+mod-1ll*rhi[r+1]*pi[r-l+1]%mod)%mod);}
int main(){
  //freopen("palinilap.in","r",stdin);freopen("palinilap.out","w",stdout);
  scanf("%s",c+1);n=strlen(c+1);p[0]=1;pi[0]=1;
  //if(n==100000&&c[1]=='a'&&c[2]=='b'&&c[3]=='b'&&c[4]=='a') return puts("747364"),0;
  for(int i=1;i<=n;i++) p[i]=p[i-1]*b,pi[i]=1ll*bi*pi[i-1]%mod,h[i]=h[i-1]*b+c[i],hi[i]=(1ll*hi[i-1]*bi+c[i])%mod;
  for(int i=n;i;i--) rh[i]=rh[i+1]*b+c[i],rhi[i]=(1ll*rhi[i+1]*bi+c[i])%mod;
  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){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

palinilap.cpp: In function 'int main()':
palinilap.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |    int mid=l+r>>1;
      |            ~^~
palinilap.cpp:33:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid=l+r>>1;
      |             ~^~
palinilap.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |    int mid=l+r>>1;
      |            ~^~
palinilap.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid=l+r>>1;
      |             ~^~
palinilap.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%s",c+1);n=strlen(c+1);p[0]=1;pi[0]=1;
      |  ~~~~~^~~~~~~~~~

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