oj.uz

답안 #104890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104890 2019-04-09T13:22:06 Z Shtef Palinilap (COI16_palinilap) C++14
100 / 100
 197 ms 32864 KB 
#include <iostream>

using namespace std;

typedef long long ll;

string s;
int n, cnt1[100005], cnt2[100005];
ll frbr[100005], bcbr[100005], frsum[100005], bcsum[100005], b[100005], kolko[100005][30];
ll frh1[100005], frh2[100005], bch1[100005], bch2[100005], pot1[100005], pot2[100005];
const ll mod = (ll)1e9 + 7;
const ll B1 = 100003LL;
const ll B2 = 13337LL;

bool same(int prvix, int prviy, int drugix, int drugiy){
	if((frh1[prviy] - (frh1[prvix - 1] * pot1[prviy - prvix + 1]) % mod + mod) % mod != (bch1[drugiy] - (bch1[drugix + 1] * pot1[drugix - drugiy + 1]) % mod + mod) % mod)
		return 0;
	if((frh2[prviy] - (frh2[prvix - 1] * pot2[prviy - prvix + 1]) % mod + mod) % mod != (bch2[drugiy] - (bch2[drugix + 1] * pot2[drugix - drugiy + 1]) % mod + mod) % mod)
		return 0;
	return 1;
}

ll brojpalin(){
	ll ret = 0;
	for(int i = 1 ; i <= n ; ++i){
		int l = 0, r = min(i - 1, n - i);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i - 1, i + mid, i + 1)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		ret += l + 1;
		int x = i - l, y = i + l;
		//cout << x << ' ' << i << " - " << y << ' ' << i << " : " << l << endl;
		frbr[x]++;
		frbr[i]--;
		bcbr[y]++;
		bcbr[i]--;
		frsum[i] -= l;
		bcsum[i] -= l;
		x--;
		y++;
		if(x <= 0 || y > n)
			continue;
		int poc = l;
		r = min(i - 1, n - i);
		l = min(r, l + 1);
		//cout << l << " - : - " << r << ".-." << poc << endl;
		while(l < r){
			int mid = (l + r + 1) / 2;
			//cout << mid << "::" << same(i - mid, i - poc - 2, i + mid, i + poc + 2) << endl;
			if(same(i - mid, i - poc - 2, i + mid, i + poc + 2)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		ll cnt = l - poc;
		//cout << i << ' ' << l << ' ' << poc << endl;
		kolko[x][s[y - 1] - 'a'] += cnt;
		kolko[y][s[x - 1] - 'a'] += cnt;
	}
	for(int i = 1 ; i < n ; ++i){
		int l = -1, r = min(i - 1, n - i - 1);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i, i + mid + 1, i + 1)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		ret += l + 1;
		int x = i - l, y = i + l + 1;
		//cout << x << ' ' << i + 1 << " - " << y << ' ' << i << " : " << l << endl;
		frbr[x]++;
		frbr[i + 1]--;
		bcbr[y]++;
		bcbr[i]--;
		frsum[i + 1] -= (l + 1);
		bcsum[i] -= (l + 1);
		x--;
		y++;
		if(x <= 0 || y > n)
			continue;
		int poc = l;
		r = min(i - 1, n - i - 1);
		l = min(r, l + 1);
		while(l < r){
			int mid = (l + r + 1) / 2;
			if(same(i - mid, i - poc - 2, i + mid + 1, i + poc + 3)){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		//cout << endl;
		ll cnt = l - poc;
		kolko[x][s[y - 1] - 'a'] += cnt;
		kolko[y][s[x - 1] - 'a'] += cnt;
	}
	return ret;
}

void inithash(){
	for(int i = 1 ; i <= n ; ++i){
		frh1[i] = (frh1[i - 1] * B1 + s[i - 1] - 'a' + 1) % mod;
		frh2[i] = (frh2[i - 1] * B2 + s[i - 1] - 'a' + 1) % mod;
	}
	for(int i = n ; i >= 1 ; --i){
		bch1[i] = (bch1[i + 1] * B1 + s[i - 1] - 'a' + 1) % mod;
		bch2[i] = (bch2[i + 1] * B2 + s[i - 1] - 'a' + 1) % mod;
	}
	pot1[0] = pot2[0] = 1;
	for(int i = 1 ; i <= n ; ++i){
		pot1[i] = (pot1[i - 1] * B1) % mod;
		pot2[i] = (pot2[i - 1] * B2) % mod;
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
n = (int)s.size();
inithash();
ll sve = brojpalin();
ll sad = 0, cnt = 0;
for(int i = 1 ; i <= n ; ++i){
	//cout << frbr[i] << ' ';
	cnt += frbr[i];
	sad += frsum[i];
	sad += cnt;
	b[i] += sad;
	//cout << b[i] << ' ';
}
//cout << endl;
sad = 0;
cnt = 0;
for(int i = n ; i >= 1 ; --i){
	cnt += bcbr[i];
	sad += bcsum[i];
	sad += cnt;
	b[i] += sad;
}
/*
for(int i = 1 ; i <= n ; ++i){
	cout << b[i] << ' ';
}
*/
ll sol = sve;
//cout << sol << endl;
for(int i = 1 ; i <= n ; ++i){
	ll maxi = 0;
	for(int j = 0 ; j < 26 ; ++j){
		if(j == s[i - 1] - 'a')
			continue;
		maxi = max(maxi, (ll)kolko[i][j]);
	}
	sol = max(sol, sve - b[i] + maxi);
}
cout << sol << endl;

return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 10 ms 2048 KB Output is correct
4 Correct 6 ms 1380 KB Output is correct
5 Correct 6 ms 1792 KB Output is correct
6 Correct 3 ms 2048 KB Output is correct
7 Correct 6 ms 2048 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 32796 KB Output is correct
2 Correct 193 ms 32632 KB Output is correct
3 Correct 156 ms 32632 KB Output is correct
4 Correct 145 ms 32632 KB Output is correct
5 Correct 148 ms 32692 KB Output is correct
6 Correct 149 ms 32652 KB Output is correct
7 Correct 152 ms 32864 KB Output is correct
8 Correct 112 ms 9244 KB Output is correct
9 Correct 148 ms 32836 KB Output is correct
10 Correct 138 ms 32632 KB Output is correct
11 Correct 182 ms 32632 KB Output is correct
12 Correct 132 ms 32632 KB Output is correct
13 Correct 175 ms 32616 KB Output is correct
14 Correct 145 ms 32668 KB Output is correct
15 Correct 138 ms 32632 KB Output is correct
16 Correct 197 ms 32620 KB Output is correct
17 Correct 134 ms 32760 KB Output is correct
18 Correct 172 ms 32732 KB Output is correct
19 Correct 121 ms 32760 KB Output is correct