Submission #97287

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
97287	2019-02-14 18:59:54	dalgerok	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	176 ms	28940 KiB

palindromic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, MOD1 = 1e9 + 1337, MOD2 = 999888777;
string s;
int n, p1[N], p2[N], h1[N], h2[N];
inline pair < int, int > get_hash(int l, int r){
    int cur1 = 1LL * (h1[r] - h1[l - 1] + MOD1) % MOD1 * p1[N - r] % MOD1,
        cur2 = 1LL * (h2[r] - h2[l - 1] + MOD2) % MOD2 * p2[N - r] % MOD2;
    return make_pair(cur1, cur2);
}
inline void solve(){
    cin >> s;
    n = (int)s.size();
    s = '#' + s;
    for(int i = 1; i <= n; i++){
        h1[i] = (h1[i - 1] + 1LL * (s[i] - 'a' + 1) * p1[i] % MOD1) % MOD1;
        h2[i] = (h2[i - 1] + 1LL * (s[i] - 'a' + 1) * p2[i] % MOD2) % MOD2;
    }
    int l = 1, r = n, ans = 0;
    while(l <= r){
        for(int len = 1; l + len - 1 < r - len + 1; len++){
            if(get_hash(l, l + len - 1) == get_hash(r - len + 1, r)){
                ans += 2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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