oj.uz

Submission #561165

# Submission time Handle Problem Language Result Execution time Memory
561165 2022-05-12T12:02:22 Z fatemetmhr Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 310 ms 28456 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb      push_back
#define all(x)  x.begin(), x.end()
#define fi      first
#define se      second

const int maxn5 = 1e6 + 10;

ll base[2] = {31, 37};
ll mod[2]  = {1000000009, 1000000007};

int hass[2][maxn5], pw[2][maxn5];

inline bool is_eq(int l1, int r1, int l2, int r2){
    for(int j = 0; j < 2; j++){
        ll tmp1, tmp2;
        tmp1 = (mod[j] + hass[j][r1] - (l1 > 0 ? ll(hass[j][l1 - 1]) * pw[j][r1 - l1 + 1] % mod[j] : 0)) % mod[j];
        tmp2 = (mod[j] + hass[j][r2] - (l2 > 0 ? ll(hass[j][l2 - 1]) * pw[j][r2 - l2 + 1] % mod[j] : 0)) % mod[j];
        if(tmp1 != tmp2)
            return false;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    for(int j = 0; j < 2; j++){
        pw[j][0] = 1;
        for(int i = 1; i < maxn5; i++)
            pw[j][i] = pw[j][i - 1] * base[j] % mod[j];
    }

    int tt; cin >> tt;
    while(tt--){
        string s; cin >> s;
        int n = s.size();
        ll last[2] = {0, 0};
        for(int j = 0; j < 2; j++) for(int i = 0; i < n; i++){
            last[j] = (last[j] * base[j] + s[i] - 'a' + 1) % mod[j];
            hass[j][i] = last[j];
        }
        int ans = 0;
        int fr = 0;
        for(int i = 0; i < n; i++){
            if((i - fr + 1) * 2 > n - fr){
                ans++;
                break;
            }
            if(is_eq(fr, i, n - (i - fr + 1), n - 1)){
                ans += 2;
                n -= i - fr + 1;
                fr = i + 1;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8108 KB Output is correct
2 Correct 16 ms 8100 KB Output is correct
3 Correct 16 ms 8156 KB Output is correct
4 Correct 16 ms 8164 KB Output is correct
5 Correct 17 ms 8148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8108 KB Output is correct
2 Correct 16 ms 8100 KB Output is correct
3 Correct 16 ms 8156 KB Output is correct
4 Correct 16 ms 8164 KB Output is correct
5 Correct 17 ms 8148 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 18 ms 8148 KB Output is correct
8 Correct 16 ms 8196 KB Output is correct
9 Correct 14 ms 8132 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8108 KB Output is correct
2 Correct 16 ms 8100 KB Output is correct
3 Correct 16 ms 8156 KB Output is correct
4 Correct 16 ms 8164 KB Output is correct
5 Correct 17 ms 8148 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 18 ms 8148 KB Output is correct
8 Correct 16 ms 8196 KB Output is correct
9 Correct 14 ms 8132 KB Output is correct
10 Correct 18 ms 8288 KB Output is correct
11 Correct 18 ms 8300 KB Output is correct
12 Correct 18 ms 8276 KB Output is correct
13 Correct 18 ms 8244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8108 KB Output is correct
2 Correct 16 ms 8100 KB Output is correct
3 Correct 16 ms 8156 KB Output is correct
4 Correct 16 ms 8164 KB Output is correct
5 Correct 17 ms 8148 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 18 ms 8148 KB Output is correct
8 Correct 16 ms 8196 KB Output is correct
9 Correct 14 ms 8132 KB Output is correct
10 Correct 18 ms 8288 KB Output is correct
11 Correct 18 ms 8300 KB Output is correct
12 Correct 18 ms 8276 KB Output is correct
13 Correct 18 ms 8244 KB Output is correct
14 Correct 310 ms 28456 KB Output is correct
15 Correct 186 ms 23404 KB Output is correct
16 Correct 288 ms 27464 KB Output is correct
17 Correct 199 ms 18920 KB Output is correct