oj.uz

Submission #110796

# Submission time Handle Problem Language Result Execution time Memory
110796 2019-05-12T09:10:49 Z someone_aa Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 498 ms 29644 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
const ll mod = 1000000007;
const ll p = 61;
ll pref[N], inv[N];
string code;

void init(string x) {
    x = "a" + x;
    pref[1] = x[1]-'a'+1;
    ll pp = p;
    for(int i=2;i<x.length();i++) {
        pref[i] = 1LL*(pref[i-1]+((x[i]-'a'+1)*pp)%mod)%mod;
        pp *= p; pp%=mod;
    }
}

ll power(ll a, ll b) {
    if(b==0) return 1LL;
    else if(b==1) return 1LL*(a%mod);
    else {
        if(b%2==1) {
            ll temp = power(a, b-1);
            return (a*temp)% mod;
        }
        else {
            ll temp = power(a, b/2);
            return (temp*temp)%mod;
        }
    }
}

ll calc_mod(ll a) {
    return 1LL*(a%mod + mod)%mod;
}

ll get_hash(int li, int ri) {
    ll x = pref[ri+1]-pref[li];
    x = calc_mod(x);
    ll y = inv[li];
    return 1LL*(x*y) % mod;
}

int solve(string x) {
    if(x.length()==1) {
        return 1;
    }

    memset(pref,0,sizeof(pref));
    init(x);
    int n = x.length();
    int l1 = 0, r1=0;
    int l2 = n-1, r2=n-1;

    int br = 0;
    while(true) {
        if(r1+1==l2) {
            br++;
            if(get_hash(l1,r1) == get_hash(l2,r2)) br++;
            break;
        }

        if(r1+1==l2-1) {
            br++;
            if(get_hash(l1,r1) == get_hash(l2,r2)) br+=2;
            break;
        }

        if(get_hash(l1, r1) == get_hash(l2, r2)) {
            br+=2;
            l1 = r1 = r1+1;
            l2 = r2 = l2-1;
        }
        else {
            r1++;
            l2--;
        }
    }
    return br;
}

void init_start() {
    ll pp = 1LL;
    for(int i=0;i<N;i++) {
        inv[i] = power(pp, mod-2);
        pp *= p; pp%=mod;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    init_start();
    int te;
    cin>>te;
    while(te--) {
        cin>>code;
        cout<<solve(code)<<"\n";
    }
    return 0;
}

Compilation message

palindromic.cpp: In function 'void init(std::__cxx11::string)':
palindromic.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<x.length();i++) {
                 ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 16120 KB Output is correct
2 Correct 291 ms 16120 KB Output is correct
3 Correct 319 ms 16020 KB Output is correct
4 Correct 287 ms 15996 KB Output is correct
5 Correct 319 ms 15992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 16120 KB Output is correct
2 Correct 291 ms 16120 KB Output is correct
3 Correct 319 ms 16020 KB Output is correct
4 Correct 287 ms 15996 KB Output is correct
5 Correct 319 ms 15992 KB Output is correct
6 Correct 305 ms 15972 KB Output is correct
7 Correct 305 ms 16064 KB Output is correct
8 Correct 313 ms 16068 KB Output is correct
9 Correct 330 ms 15980 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 16120 KB Output is correct
2 Correct 291 ms 16120 KB Output is correct
3 Correct 319 ms 16020 KB Output is correct
4 Correct 287 ms 15996 KB Output is correct
5 Correct 319 ms 15992 KB Output is correct
6 Correct 305 ms 15972 KB Output is correct
7 Correct 305 ms 16064 KB Output is correct
8 Correct 313 ms 16068 KB Output is correct
9 Correct 330 ms 15980 KB Output is correct
10 Correct 304 ms 16160 KB Output is correct
11 Correct 305 ms 16144 KB Output is correct
12 Correct 304 ms 16248 KB Output is correct
13 Correct 296 ms 16152 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 16120 KB Output is correct
2 Correct 291 ms 16120 KB Output is correct
3 Correct 319 ms 16020 KB Output is correct
4 Correct 287 ms 15996 KB Output is correct
5 Correct 319 ms 15992 KB Output is correct
6 Correct 305 ms 15972 KB Output is correct
7 Correct 305 ms 16064 KB Output is correct
8 Correct 313 ms 16068 KB Output is correct
9 Correct 330 ms 15980 KB Output is correct
10 Correct 304 ms 16160 KB Output is correct
11 Correct 305 ms 16144 KB Output is correct
12 Correct 304 ms 16248 KB Output is correct
13 Correct 296 ms 16152 KB Output is correct
14 Correct 482 ms 29644 KB Output is correct
15 Correct 400 ms 24272 KB Output is correct
16 Correct 498 ms 29132 KB Output is correct
17 Correct 409 ms 23248 KB Output is correct