oj.uz

Submission #915862

# Submission time Handle Problem Language Result Execution time Memory
915862 2024-01-24T19:33:41 Z rahidilbayramli Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 287 ms 18980 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 1e6+5, mod = 1e9+7, P = 47;
ll p[sz], h[sz], n, i;
bool check(ll a, ll b, ll k)
{
    ll h1 = (h[a + k - 1] - h[a - 1] + mod) % mod;
    ll h2 = (h[b + k - 1] - h[b - 1] + mod) % mod;
    return (h1 * 1LL * p[b - a]) % mod == h2;
}
int main()
{
    ll tests = 1;
    cin >> tests;
    while(tests--)
    {
        string s;
        cin >> s;
        n = s.size();
        p[0] = 1;
        for(i = 1; i <= n; i++)
            p[i] = (p[i-1] * P * 1LL) % mod;
        for(i = 1; i <= n; i++)
            h[i] = (h[i-1] + ((s[i - 1] - 'a' + 1) * 1LL * p[i-1])) % mod;
        ll ans = 0, l = 1, r = n, k = 1, curl = -1, curr = -1;
        while(l < r)
        {
            ll a = l - k + 1;
            if(check(a, r, k))
            {
                ans++;
                k = 1;
                curl = l;
                curr = r;
            }
            else
                k++;
            l++;
            r--;
        }
        if(curl + 1 == curr)
            cout << ans * 2 << "\n";
        else
            cout << ans * 2 + 1 << "\n";
        for(i = 0; i <= n; i++)
        {
            h[i] = 0;
            p[i] = 0;
        }
        n = 0;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2460 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2460 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2460 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 2 ms 2392 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2460 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 2 ms 2392 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 287 ms 18980 KB Output is correct
15 Correct 154 ms 18812 KB Output is correct
16 Correct 280 ms 18836 KB Output is correct
17 Correct 154 ms 12316 KB Output is correct