oj.uz

Submission #592848

# Submission time Handle Problem Language Result Execution time Memory
592848 2022-07-09T16:47:38 Z VasLemmy Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 240 ms 42460 KB 
/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;

#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

const pii mod = {1000000007,123456791};
const int maxN = 1000005;
const int base = 31;

int n;
string s;
pii prehash[maxN];
pii powr[maxN];

void Prepare()
{
    powr[0] = {1,1};
    for(int i = 1;i < maxN;i++)
    {
        powr[i].fi = powr[i-1].fi * base % mod.fi;
        powr[i].se = powr[i-1].se * base % mod.se;
    }
}

pii Gethash(int l,int r)
{
    pii res;
    res.fi = (prehash[r].fi - prehash[l-1].fi * powr[r-l+1].fi % mod.fi) % mod.fi;
    if(res.fi < 0) res.fi += mod.fi;
    res.se = (prehash[r].se - prehash[l-1].se * powr[r-l+1].se % mod.se) % mod.se;
    if(res.se < 0) res.se += mod.se;
    return res;
}

void read()
{
    cin >> s;
    n = s.size();
    s.insert(0,"?");
    for(int i = 1;i <= n;i++)
    {
        prehash[i].fi = (prehash[i-1].fi * base % mod.fi + (s[i] - 'a' + 1)) % mod.fi;
        prehash[i].se = (prehash[i-1].se * base % mod.se + (s[i] - 'a' + 1)) % mod.se;
    }
    int res = 0;
    int L = 1;
    int R = n;
    int len = 1;
    while(true)
    {
        int l1,r1,l2,r2;
        l1 = L;
        r1 = l1 + len - 1;
        l2 = R - len + 1;
        r2 = R;
        if(L > R) {cout << res <<'\n';return;}
        if(l2 <= r1) {cout << res + 1 <<'\n';return;}
        if(Gethash(l1,r1) == Gethash(l2,r2))
        {
            res += 2;
            L = r1 + 1;
            R = l2 - 1;
            len = 1;
        }
        else
        {
            len++;
        }
    }

}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    Prepare();
    int tests;
    cin >> tests;
    //ests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15956 KB Output is correct
2 Correct 13 ms 15996 KB Output is correct
3 Correct 13 ms 15976 KB Output is correct
4 Correct 13 ms 15956 KB Output is correct
5 Correct 13 ms 15992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15956 KB Output is correct
2 Correct 13 ms 15996 KB Output is correct
3 Correct 13 ms 15976 KB Output is correct
4 Correct 13 ms 15956 KB Output is correct
5 Correct 13 ms 15992 KB Output is correct
6 Correct 13 ms 15956 KB Output is correct
7 Correct 16 ms 15968 KB Output is correct
8 Correct 14 ms 15956 KB Output is correct
9 Correct 16 ms 15956 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15956 KB Output is correct
2 Correct 13 ms 15996 KB Output is correct
3 Correct 13 ms 15976 KB Output is correct
4 Correct 13 ms 15956 KB Output is correct
5 Correct 13 ms 15992 KB Output is correct
6 Correct 13 ms 15956 KB Output is correct
7 Correct 16 ms 15968 KB Output is correct
8 Correct 14 ms 15956 KB Output is correct
9 Correct 16 ms 15956 KB Output is correct
10 Correct 16 ms 16264 KB Output is correct
11 Correct 15 ms 16132 KB Output is correct
12 Correct 17 ms 16256 KB Output is correct
13 Correct 14 ms 16224 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15956 KB Output is correct
2 Correct 13 ms 15996 KB Output is correct
3 Correct 13 ms 15976 KB Output is correct
4 Correct 13 ms 15956 KB Output is correct
5 Correct 13 ms 15992 KB Output is correct
6 Correct 13 ms 15956 KB Output is correct
7 Correct 16 ms 15968 KB Output is correct
8 Correct 14 ms 15956 KB Output is correct
9 Correct 16 ms 15956 KB Output is correct
10 Correct 16 ms 16264 KB Output is correct
11 Correct 15 ms 16132 KB Output is correct
12 Correct 17 ms 16256 KB Output is correct
13 Correct 14 ms 16224 KB Output is correct
14 Correct 240 ms 42460 KB Output is correct
15 Correct 141 ms 37872 KB Output is correct
16 Correct 214 ms 41916 KB Output is correct
17 Correct 130 ms 30056 KB Output is correct