Submission #241921

#	Time	Username	Problem	Language	Result	Execution time	Memory
241921		BamiTorabi	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	154 ms	26876 KiB

palindromic

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e6 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
ll sq(ll x) {return (x * x) % MOD;}
ll modP(ll a, ll b) {return (!b ? 1 : (sq(modP(a, b / 2)) * (b % 2 ? a : 1)) % MOD);}

ll base = 619, H[maxN];
ll pw[maxN];

ll hsh(int l, int r){
	return (H[r] - H[l] * pw[r - l] % MOD + MOD) % MOD;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	pw[0] = 1;
	for (int i = 1; i < maxN; i++){
		pw[i] = (pw[i - 1] * base) % MOD;
	}
	int Q; cin >> Q;
	string s;
	while (Q--){
		cin >> s;
		int n = s.size();
		for (int i = 1; i <= n; i++){
			H[i] = (H[i - 1] * base + (s[i - 1] - 'a')) % MOD;
		}
		int l = 0, r = n;
		int x = 1;
		int ans = 0;
		while (r > l){
			if (hsh(l, l + x) == hsh(r - x, r)){
				ans += 1 + (l + x != r);
				l += x;
				r -= x;
				x = 1;
			}
			else x++;
		}
		cout << ans << "\n";
	}
	return 0;
}
 

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40