oj.uz

Submission #446513

# Submission time Handle Problem Language Result Execution time Memory
446513 2021-07-22T08:40:57 Z JasperL Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 413 ms 27816 KB 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define maxn 1000005
typedef long long ll;
ll mod = 1e9 + 7;
ll p = 29;

string s; int n; vector<int> ret;
ll h[maxn]; // hash values
ll pw[maxn];

bool match(int i, int j, int len) {
    // if [i ... i+len) == [j ... j+len)
    ll H1 = h[i+len-1] - pw[len] * h[i-1]; H1 %= mod; if (H1 < 0) H1 += mod;
    ll H2 = h[j+len-1] - pw[len] * h[j-1]; H2 %= mod; if (H2 < 0) H2 += mod;
    return H1 == H2;
}

void solve() {
    n = s.length(); s = '$' + s;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * p + (s[i]-'a'); h[i] %= mod;
    }
    int l = 1, r = n;
    int ans = 0;
    for (int i = 1, j = n; i < j; i++, j--) {
        if (match(l,j,i-l+1)) {
            ans += 2; l = i+1; r = j-1; continue;
        }
    }   
    if (l <= r) ans++;
    ret.push_back(ans);
}  

int main() {
    int t; cin >> t; 
    pw[0] = 1;
    for (int i = 1; i < maxn; i++) pw[i] = (pw[i-1] * p)%mod;
    for (int i = 0; i < t; i++) {
        cin >> s; solve();
    }
    for (int z : ret) cout << z << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 10 ms 8012 KB Output is correct
3 Correct 10 ms 8140 KB Output is correct
4 Correct 10 ms 8132 KB Output is correct
5 Correct 10 ms 8056 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 10 ms 8012 KB Output is correct
3 Correct 10 ms 8140 KB Output is correct
4 Correct 10 ms 8132 KB Output is correct
5 Correct 10 ms 8056 KB Output is correct
6 Correct 10 ms 8012 KB Output is correct
7 Correct 11 ms 8036 KB Output is correct
8 Correct 10 ms 8140 KB Output is correct
9 Correct 9 ms 8104 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 10 ms 8012 KB Output is correct
3 Correct 10 ms 8140 KB Output is correct
4 Correct 10 ms 8132 KB Output is correct
5 Correct 10 ms 8056 KB Output is correct
6 Correct 10 ms 8012 KB Output is correct
7 Correct 11 ms 8036 KB Output is correct
8 Correct 10 ms 8140 KB Output is correct
9 Correct 9 ms 8104 KB Output is correct
10 Correct 14 ms 8280 KB Output is correct
11 Correct 12 ms 8268 KB Output is correct
12 Correct 14 ms 8252 KB Output is correct
13 Correct 13 ms 8276 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8140 KB Output is correct
2 Correct 10 ms 8012 KB Output is correct
3 Correct 10 ms 8140 KB Output is correct
4 Correct 10 ms 8132 KB Output is correct
5 Correct 10 ms 8056 KB Output is correct
6 Correct 10 ms 8012 KB Output is correct
7 Correct 11 ms 8036 KB Output is correct
8 Correct 10 ms 8140 KB Output is correct
9 Correct 9 ms 8104 KB Output is correct
10 Correct 14 ms 8280 KB Output is correct
11 Correct 12 ms 8268 KB Output is correct
12 Correct 14 ms 8252 KB Output is correct
13 Correct 13 ms 8276 KB Output is correct
14 Correct 405 ms 27744 KB Output is correct
15 Correct 222 ms 22932 KB Output is correct
16 Correct 413 ms 27816 KB Output is correct
17 Correct 211 ms 18356 KB Output is correct