Submission #138874

#	Time	Username	Problem	Language	Result	Execution time	Memory
138874		alishahali1382	Palinilap (COI16_palinilap)	C++14	100 / 100	121 ms	24384 KiB

palinilap

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, B=10007;

ll n, m, k, u, v, x, y, t, a, b, ans, pal;
char A[MAXN];
ll hl[MAXN], hr[MAXN], tav[MAXN];
ll ps1[MAXN];
ll cnt[MAXN][26];

ll getl(int l, int r){
	ll res=(hl[r]-hl[l-1]*tav[r-l+1])%mod;
	return (res+mod)%mod;
}

ll getr(int l, int r){
	ll res=(hr[l]-hr[r+1]*tav[r-l+1])%mod;
	return (res+mod)%mod;
}

bool check(int l1, int r1, int l2, int r2){
	if (min(l1, l2)<1 || n<max(r1, r2)) return 0;
	//debug("shit")
	return getl(l1, r1)==getr(l2, r2);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s;
	cin>>s;
	n=s.size();
	for (int i=1; i<=n; i++) A[i]=s[i-1];
	for (int i=1; i<=n; i++) hl[i]=(hl[i-1]*B+A[i])%mod;
	for (int i=n; i; i--) hr[i]=(hr[i+1]*B+A[i])%mod;
	tav[0]=1;
	for (int i=1; i<=n; i++) tav[i]=tav[i-1]*B%mod;
	
	/*
	// ---------------------------------------------------
	
	for (int i=0; i<=n; i++) cerr<<hl[i]<<" \n"[i==n];

	debug(check(1, 1, 2, 2))
	debug(getl(1, 1))
	debug(getl(2, 2))
	*/
	
	/// even lenth
	for (int i=1; i<=n; i++){
		int dwn=0, up=n+1;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(i-mid+1, i, i+1, i+mid)) dwn=mid;
			else up=mid;
		}
		int len=dwn, l=i-len+1, r=i+len;
		
		//debug2(i, len)
		if (len){ 	
		ps1[l]++;
		ps1[i+1]--;
		ps1[i+2]--;
		ps1[r+2]++;
		//debug2(l, r)
		}
		// tof can be deleted		

		pal+=len;
		if (l<=1 || r>=n) continue ;
		
		dwn=0, up=n;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(l-1-mid, l-2, r+2, r+1+mid)) dwn=mid;
			else up=mid;
		}
		cnt[l-1][A[r+1]-'a']+=dwn+1;
		cnt[r+1][A[l-1]-'a']+=dwn+1;
	}
	
	
	// odd lenth
	for (int i=1; i<=n; i++){
		int dwn=0, up=n+1;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(i-mid, i-1, i+1, i+mid)) dwn=mid;
			else up=mid;
		}
		int len=dwn, l=i-len, r=i+len;

		//debug2(i, len)

		ps1[l]++;
		ps1[i]-=len+1;
		ps1[i+1]+=len*2;
		ps1[i+2]-=len+1;
		ps1[r+2]++;

		pal+=len+1;
		if (l<=1 || r>=n) continue ;
		
		dwn=0, up=n;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (check(l-1-mid, l-2, r+2, r+1+mid)) dwn=mid;
			else up=mid;
		}
		cnt[l-1][A[r+1]-'a']+=dwn+1;
		cnt[r+1][A[l-1]-'a']+=dwn+1;
	}
	// ----------
	
	

	for (int i=1; i<=n; i++) ps1[i]+=ps1[i-1];
	for (int i=1; i<=n; i++) ps1[i]+=ps1[i-1];
	//for (int i=1; i<=n; i++) cerr<<ps1[i]<<" \n"[i==n];

	ans=pal;
	for (int i=1; i<=n; i++) for (int c=0; c<26; c++) ans=max(ans, pal-ps1[i]+cnt[i][c]);
	cout<<ans<<'\n';
	
	return 0;
}

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