Submission #320394

#	Time	Username	Problem	Language	Result	Execution time	Memory
320394		suto	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	214 ms	28584 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef string str;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define pb(x)                       push_back(x)
#define pf(x)                       push_front(x)
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll MAXN = 1e6 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

ll po[MAXN] , hsh[MAXN];

int main(){

    fast_io;
    po[0] = 1;
    for(int i = 1; i < MAXN; i++){
        po[i] = po[i - 1] * 737 % MOD;
    }
    ll t;
    cin >> t;
    while (t --){
        str s;
        cin >> s;
        ll n = s.size();
        for(int i = 1; i <= n; i++){
            hsh[i] = (hsh[i - 1] * 737 % MOD + (s[i - 1] - 'a' + 1))% MOD;
        }
        ll l = 1 , r = n , ans = 0;
        while(r >= l){
            ll v = l , u = r;
            bool d = false;
            while(u > v){
                if((hsh[v] - hsh[l - 1] * po[v - l + 1] % MOD + MOD) % MOD == (hsh[r] - hsh[u - 1] * po[r - u + 1] % MOD + MOD) % MOD){
                    v ++;
                    u --;
                    ans += 2;
                    d = true;
                    break;
                }
                v ++;
                u --;
            }
            if(!d){
                ans ++;
                break;
            }
            l = v;
            r = u;
        }
        cout << ans << endl;
    }

}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40