oj.uz

Submission #482931

# Submission time Handle Problem Language Result Execution time Memory
482931 2021-10-26T19:27:44 Z MohamedAliSaidane Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 1041 ms 29000 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (ll)(1000000007)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}

ll mod(ll a, ll m)
{
    return ((a%m)+m)%m;
}
ll modInverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
        return 0;
    while (a > 1) {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
        x += m0;
    return x;
}
////////////******SOLUTION******\\\\\\\\\\\

string s, t;
int n;
ll p = 131ll;
vll P;
vll h;
ll hash_fast(int l, int r)
{
    if(l == 0)
        return h[r];
    ll ans = 0;
    ans = ((h[r] - h[l-1])%MOD + MOD)%MOD;
    ans = ((ll)ans*modInverse(P[l],MOD))%MOD;
    //cout << "here\n" << flush;
    return ans;
}
void solve()
{
    cin >> s;
    n = s.length();
    P.assign(n,0ll);
    P[0] = 1ll;
    h.assign(n,0ll);
    for(int i = 1;i <n; i++)
    {
        P[i] = ((ll)(P[i-1]*p))% MOD;
    }
    for(int i = 0; i < n; i ++)
    {
        if(i != 0)
        h[i] = h[i-1];
        h[i] = (h[i]+((ll)s[i]*P[i])%MOD)%MOD;
        //cout << h[i] << ' ';
    }
    //cout << '\n';
    int ans = 0;
    int i = 0;
    while(i <= n/2-1 + n%2)
    {
        //cout << i << ' ' << flush;
        if(s[i] != s[n-i-1])
        {
            int u = 1;
            ll pr = hash_fast(i,i+u);
            ll dup = hash_fast(n-i-u-1,n-i-1);
            while(pr != dup)
            {
                u ++;
                pr = hash_fast(i,i+u);
                dup = hash_fast(n-i-u-1,n-i-1);
            }
            i += u;
        }
        ans += 2;
        if(i >= n/2)
            ans --;
        i ++;
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt; cin >> tt;
    while(tt--)
        solve();
}

Compilation message

palindromic.cpp:46:1: warning: multi-line comment [-Wcomment]
   46 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 7 ms 536 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Correct 6 ms 460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 7 ms 536 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Correct 6 ms 460 KB Output is correct
14 Correct 619 ms 24124 KB Output is correct
15 Correct 412 ms 29000 KB Output is correct
16 Correct 1041 ms 27620 KB Output is correct
17 Correct 345 ms 14260 KB Output is correct