Submission #374180

#	Time	Username	Problem	Language	Result	Execution time	Memory
374180		srvlt	Palinilap (COI16_palinilap)	C++17	100 / 100	186 ms	25068 KiB

palinilap

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cerr if(dbg)cerr
using namespace std;

const int n0=1e5+123;
int n;
string s;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace Sol {
	bool dbg=0;
	ll mul[n0],add[n0],positive[n0][26],init;
	namespace Hash {
		const array<int,2> mod={(int)1e9+7,(int)1e9+9};
		int base=uniform_int_distribution<int>(27,(int)1e9)(rng);
		struct mint {
			array<int,2> x;
			mint(int val=0) {
				x[0]=x[1]=val;
			}
			void operator *= (const mint &a) {
				x[0]=(ll)x[0]*a.x[0]%mod[0];
				x[1]=(ll)x[1]*a.x[1]%mod[1];
			}
			void operator += (const mint &a) {
				x[0]+=a.x[0];if(x[0]>=mod[0]) x[0]-=mod[0];
				x[1]+=a.x[1];if(x[1]>=mod[1]) x[1]-=mod[1];
			}
			void operator -= (const mint &a) {
				x[0]-=a.x[0];if(x[0]<0) x[0]+=mod[0];
				x[1]-=a.x[1];if(x[1]<0) x[1]+=mod[1];
			}
			mint operator * (const mint &a) {
				mint res=*this;
				res*=a;
				return res;
			}
			mint operator + (const mint &a) {
				mint res=*this;
				res+=a;
				return res;
			}
			mint operator - (const mint &a) {
				mint res=*this;
				res-=a;
				return res;
			}
			bool operator == (const mint &a) {
				return x[0]==a.x[0] && x[1]==a.x[1];
			}
		};
		mint pref[n0],suf[n0],pw[n0];
		void build() {
			pw[0]=1;
			for(int i=1; i<=n; i++) {
				pw[i]=pw[i-1]*base;
				pref[i]=pref[i-1]+pw[i]*(s[i-1]-'a'+1);
			}
			for(int i=n; i>=1; i--) {
				suf[i]=suf[i+1]+pw[n-i+1]*(s[i-1]-'a'+1);
			}
		};
		mint get(int l,int r) {
			return pw[n-r]*(pref[r]-pref[l-1]);
		}
		mint get_rev(int l,int r) {
			return pw[l-1]*(suf[l]-suf[r+1]);
		}
		void clear() {
			for(int i=0; i<n0; i++) {
				pref[i]=suf[i]=pw[i]=0;
			}
		};
	}
	bool pal(int l,int r,int l2,int r2) {
		if(l<1 || l2<1 || r>n || r2>n) return 0;
		return Hash::get(l,r)==Hash::get_rev(l2,r2);
	}
	int find(int L,int R) {
		int l=-1,r=n;
		while(l<r-1) {
			int mid=l+r>>1;
			if(pal(L-mid,L,R,R+mid)) l=mid;
			else r=mid;
		}
		return l;
	}
	void add_inc(int l,int r,int x) {
		//(x-l)+i
		add[l]+=x-l,add[r+1]-=x-l;
		mul[l]++,mul[r+1]--;
	}
	void add_dec(int l,int r,int x) {
		//(x+l)-i
		add[l]+=x+l,add[r+1]-=x+l;
		mul[l]--,mul[r+1]++;
	}
	ll get(int pos) {
		return add[pos]+mul[pos]*pos;
	}
	void process(int L,int R) {
		int a=find(L,R);
		init+=a+1;
		int b=find(L-a-2,R+a+2);
		cerr << "process(" << L << "," << R << ")={" << a << "," << b << "}\n";
		if(L-a-1>=1 && R+a+1<=n) {
			positive[L-a-1][s[R+a]-'a']+=1+(b+1);
			positive[R+a+1][s[L-a-2]-'a']+=1+(b+1);
		}
		if(a>=0) {
			cerr << "neg\n";
			cerr << "inc: " << L-a << ' ' << L << ",start=" << -1 << '\n';
			cerr << "dec: " << R << ' ' << R+a << ",start=" << -a-1 << '\n';
			add_dec(L-a,L,-1);
			add_inc(R,R+a,-a-1);
		}
	}
	void clear() {
		Hash::clear();
		mem(mul,0),mem(add,0),mem(positive,0),init=0;
	};
	ll solve(bool _dbg) {
		dbg=_dbg;
		clear();
		Hash::build();
		for(int i=1; i<=n-1; i++) process(i,i+1);
		for(int i=1; i<=n-2; i++) process(i,i+2);
		init+=n;
		ll ans=init;
		cerr << "init=" << ans << '\n';
		for(int i=1; i<=n; i++) {
			add[i]+=add[i-1];
			mul[i]+=mul[i-1];
			ll diff=get(i);
			ll cur=0;
			for(int j=0; j<26; j++) {
				cur=0;
				if(s[i-1]-'a'!=j) cur+=diff;
				cur+=positive[i][j];
				ans=max(ans,init+cur);
			}
		}
		cerr << "neg[1]=" << get(1) << '\n';
		cerr << "positive[1][1]=" << positive[1][1] << '\n';
		return ans;
	};
}
namespace Slow {
	bool dbg=0;
	ll count(string x) {
		ll res=0;
		for(int i=0; i<SZ(x); i++) {
			for(int j=i; j<SZ(x); j++) {
				int ok=1;
				for(int k=i; k<=j; k++) {
					int t=j-(k-i);
					if(x[k]!=x[t]) {
						ok=0;
						break;
					}
				}
				if(ok) {
					res++;
				}
			}
		}
		return res;
	}
	ll solve(bool _dbg) {
		ll ans=0;
		string ans_t;
		for(int i=0; i<n; i++) {
			string t=s;
			for(int j=0; j<26; j++) {
				t[i]=char('a'+j);
				ll val=count(t);
				if(ans<val) {
					ans=val;
					ans_t=t;
				}
			}
		}
		cerr << ans_t << '\n';
		return ans;
	}
}
namespace Gen {
	uniform_int_distribution<int> _n(1,5),_c(0,5);
	void gen() {
		s="";
		n=_n(rng);
		for(int i=0; i<n; i++) s+=char('a'+_c(rng));
	}
	void output() {
		cout << n << '\n';
		cout << s << '\n';
	};
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	n=SZ(s);
	//ll sol=Sol::solve(1);
	//ll slow=Slow::solve(1);
	//cout << sol << ' ' << slow;
	cout << Sol::solve(0);
	
	//int tc=100000;
	//while(tc--) {
		//Gen::gen();
		//ll sol=Sol::solve(0),slow=Slow::solve(0);
		//if(sol!=slow) {
			//cout << "WA\n";
			//Gen::output();
			//cout << "expected=" << slow << ", output=" << sol << '\n';
			//return 0;
		//}
	//}
	//cout << "OK";
}

Compilation message (stderr)

palinilap.cpp: In function 'int Sol::find(int, int)':
palinilap.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |    int mid=l+r>>1;
      |            ~^~

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