oj.uz

Submission #1011529

# Submission time Handle Problem Language Result Execution time Memory
1011529 2024-06-30T14:58:59 Z NValchanov Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 92 ms 26924 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
const ll HASH = 31;

string s;
int n;
ll h[MAXN];
ll pw[MAXN];

void read()
{
    cin >> s;
    n = s.size();
}

void fill_hash()
{
    h[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        h[i] = (h[i - 1] * HASH + (s[i - 1] - 'a' + 1)) % MOD;
    }
}

void precompute()
{
    pw[0] = 1;
    for(int i = 1; i < MAXN; i++)
    {
        pw[i] = (pw[i - 1] * HASH) % MOD;
    }
}

ll get_hash(int left, int right)
{
    return (h[right + 1] - h[left] * pw[right - left + 1] % MOD + MOD) % MOD;
}

bool compare(int left1, int right1, int left2, int right2)
{
    return get_hash(left1, right1) == get_hash(left2, right2);
}

void solve()
{
    fill_hash();

    int left = 0;
    int right = n - 1;
    int ans = 0;

    while(left <= right)
    {

        if(left == right)
        {
            ans++;
            break;
        }

        int ptr1 = left;
        int ptr2 = right;

        while(ptr1 < ptr2 && !compare(left, ptr1, ptr2, right))
        {
            ptr1++;
            ptr2--;
        }

        if(ptr1 < ptr2)
        {
            ans += 2;
        }
        else
        {
            ans++;
            break;
        }

        left = ptr1 + 1;
        right = ptr2 - 1;
    }

    cout << ans << endl;
}

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

    ll t;
    cin >> t;

    precompute();

    while(t--)
    {
        read();
        solve();
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8072 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8072 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8108 KB Output is correct
7 Correct 7 ms 8280 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8072 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8108 KB Output is correct
7 Correct 7 ms 8280 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 7 ms 8284 KB Output is correct
11 Correct 8 ms 8300 KB Output is correct
12 Correct 8 ms 8280 KB Output is correct
13 Correct 8 ms 8212 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8072 KB Output is correct
3 Correct 7 ms 8284 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8108 KB Output is correct
7 Correct 7 ms 8280 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 7 ms 8284 KB Output is correct
11 Correct 8 ms 8300 KB Output is correct
12 Correct 8 ms 8280 KB Output is correct
13 Correct 8 ms 8212 KB Output is correct
14 Correct 92 ms 26924 KB Output is correct
15 Correct 57 ms 22400 KB Output is correct
16 Correct 86 ms 26188 KB Output is correct
17 Correct 54 ms 18096 KB Output is correct