oj.uz

답안 #104889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104889 2019-04-09T13:20:49 Z Shtef Palinilap (COI16_palinilap) C++14
54 / 100
 181 ms 21116 KB 
#include <iostream>

using namespace std;

typedef long long ll;

string s;
int n, cnt1[100005], cnt2[100005], kolko[100005][30];
ll frbr[100005], bcbr[100005], frsum[100005], bcsum[100005], b[100005];
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;
			}
		}
		int 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;
		int 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 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1408 KB Output is correct
2 Correct 2 ms 1300 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 6 ms 1408 KB Output is correct
7 Correct 7 ms 1408 KB Output is correct

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 20984 KB Output is correct
2 Correct 128 ms 21008 KB Output is correct
3 Correct 124 ms 21052 KB Output is correct
4 Correct 105 ms 21116 KB Output is correct
5 Correct 100 ms 21060 KB Output is correct
6 Correct 136 ms 20984 KB Output is correct
7 Correct 130 ms 21048 KB Output is correct
8 Correct 110 ms 9328 KB Output is correct
9 Correct 147 ms 21080 KB Output is correct
10 Correct 111 ms 20984 KB Output is correct
11 Correct 144 ms 21040 KB Output is correct
12 Correct 152 ms 21112 KB Output is correct
13 Correct 122 ms 20956 KB Output is correct
14 Correct 158 ms 20956 KB Output is correct
15 Correct 140 ms 20956 KB Output is correct
16 Incorrect 181 ms 21112 KB Output isn't correct
17 Halted 0 ms 0 KB -