oj.uz

답안 #374180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374180 2021-03-06T20:22:29 Z srvlt Palinilap (COI16_palinilap) C++17
100 / 100
 186 ms 25068 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24684 KB Output is correct
2 Correct 14 ms 24684 KB Output is correct
3 Correct 14 ms 24684 KB Output is correct
4 Correct 14 ms 24684 KB Output is correct
5 Correct 14 ms 24684 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 24684 KB Output is correct
2 Correct 18 ms 24684 KB Output is correct
3 Correct 22 ms 24708 KB Output is correct
4 Correct 17 ms 24684 KB Output is correct
5 Correct 19 ms 24684 KB Output is correct
6 Correct 20 ms 24684 KB Output is correct
7 Correct 19 ms 24684 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 24916 KB Output is correct
2 Correct 118 ms 24940 KB Output is correct
3 Correct 122 ms 24940 KB Output is correct
4 Correct 178 ms 25016 KB Output is correct
5 Correct 186 ms 25068 KB Output is correct
6 Correct 166 ms 24940 KB Output is correct
7 Correct 169 ms 25068 KB Output is correct
8 Correct 92 ms 24940 KB Output is correct
9 Correct 172 ms 24940 KB Output is correct
10 Correct 177 ms 25068 KB Output is correct
11 Correct 121 ms 24940 KB Output is correct
12 Correct 176 ms 24940 KB Output is correct
13 Correct 176 ms 24940 KB Output is correct
14 Correct 167 ms 24940 KB Output is correct
15 Correct 167 ms 24940 KB Output is correct
16 Correct 140 ms 25016 KB Output is correct
17 Correct 160 ms 24940 KB Output is correct
18 Correct 168 ms 24940 KB Output is correct
19 Correct 157 ms 24940 KB Output is correct