oj.uz

답안 #531536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531536 2022-03-01T02:46:35 Z Register Palinilap (COI16_palinilap) C++14
100 / 100
 92 ms 27592 KB 
#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){
			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;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 4 ms 1704 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 3 ms 1484 KB Output is correct
6 Correct 4 ms 1612 KB Output is correct
7 Correct 4 ms 1708 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 27444 KB Output is correct
2 Correct 62 ms 27472 KB Output is correct
3 Correct 70 ms 27392 KB Output is correct
4 Correct 91 ms 27480 KB Output is correct
5 Correct 89 ms 27520 KB Output is correct
6 Correct 89 ms 27384 KB Output is correct
7 Correct 86 ms 27456 KB Output is correct
8 Correct 50 ms 7132 KB Output is correct
9 Correct 92 ms 27472 KB Output is correct
10 Correct 87 ms 27368 KB Output is correct
11 Correct 66 ms 27460 KB Output is correct
12 Correct 90 ms 27396 KB Output is correct
13 Correct 90 ms 27460 KB Output is correct
14 Correct 89 ms 27484 KB Output is correct
15 Correct 90 ms 27384 KB Output is correct
16 Correct 83 ms 27592 KB Output is correct
17 Correct 86 ms 27428 KB Output is correct
18 Correct 89 ms 27484 KB Output is correct
19 Correct 84 ms 27480 KB Output is correct