oj.uz

Submission #859477

# Submission time Handle Problem Language Result Execution time Memory
859477 2023-10-10T08:09:39 Z hoanganh_siuuuuuuuu Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 111 ms 42680 KB 
#include <bits/stdc++.h>
#define int long long
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define in insert
#define vvec vector<vector<int>>

using namespace std;

const int N = 1e6 + 5;
const int base = 311;
const int mod = 1e9 + 7;
const int mod2 = 1e6 + 3;

string s;
int n, m, t;
int Pow[N], Hash[N];
int Pow2[N], Hash2[N];

int get(int i, int j)
{
    return (Hash[j] - Hash[i - 1] * Pow[j - i + 1] + mod * mod) % mod;
}

int get2(int i, int j)
{
    return (Hash2[j] - Hash2[i - 1] * Pow2[j - i + 1] + mod2 * mod2) % mod2;
}

signed main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    Pow[0] = Pow2[0] = 1;
    f(i ,1, mod2 - 2)
    {
        Pow[i] = (Pow[i - 1] * base) % mod;
        Pow2[i] = (Pow2[i - 1] * base) % mod2;
    }
    while(t--)
    {
        cin >> s;
        n = s.size();
        s = "!" + s;
        f(i, 1, n)
        {
             Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % mod;
             Hash2[i] = (Hash2[i - 1] * base + s[i] - 'a' + 1) % mod2;
        }
        int l = 0, ok = 0, cnt = 0;
        f(i, 1, n / 2)
        {
            if(s[i] == s[n - i + 1] && l == 0)
            {
                cnt += 2;
                if(i == n / 2) ok = 1;
                //cout << i << " " << n - i + 1 << "\n";
            }
            else
            {
                if(!l) l = i;
                int j = n - l + 1;
                int k = n - i + 1;
                int left = get(l, i);
                int left2 = get2(l, i);
                int right = get(k, j);
                int right2 = get2(k, j);
                //cout << l << " " << i << " " << k << " " << j << "\n";
                //cout << left << " " << left2 << " " << right << " " << right2 << "\n";
                if(left == right && right2 == left2)
                {
                    if(i == n / 2) ok = 1;
                    l = 0;
                    //cout << "cc\n";
                    cnt += 2;
                }
            }
        }
        if(!ok || n % 2 == 1) cnt++;
        cout << cnt << "\n";
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct
6 Correct 7 ms 19544 KB Output is correct
7 Correct 7 ms 19292 KB Output is correct
8 Correct 7 ms 19188 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct
6 Correct 7 ms 19544 KB Output is correct
7 Correct 7 ms 19292 KB Output is correct
8 Correct 7 ms 19188 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 8 ms 19292 KB Output is correct
11 Correct 7 ms 19292 KB Output is correct
12 Correct 8 ms 19292 KB Output is correct
13 Correct 8 ms 19544 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19292 KB Output is correct
6 Correct 7 ms 19544 KB Output is correct
7 Correct 7 ms 19292 KB Output is correct
8 Correct 7 ms 19188 KB Output is correct
9 Correct 7 ms 19036 KB Output is correct
10 Correct 8 ms 19292 KB Output is correct
11 Correct 7 ms 19292 KB Output is correct
12 Correct 8 ms 19292 KB Output is correct
13 Correct 8 ms 19544 KB Output is correct
14 Correct 111 ms 41640 KB Output is correct
15 Correct 67 ms 37916 KB Output is correct
16 Correct 109 ms 42680 KB Output is correct
17 Correct 68 ms 33096 KB Output is correct