Submission #51957

#	Time	Username	Problem	Language	Result	Execution time	Memory
51957		Milki	Palinilap (COI16_palinilap)	C++14	54 / 100	130 ms	54160 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll BAZA = 1307;

string s;
int h[MAXN], h_[MAXN], pot[MAXN];

void calcHash(){
    pot[0] = 1;
    h[0] = s[0];

    FOR(i, 1, (int)s.size()){
        h[i] = (h[i - 1] * BAZA + s[i]) % MOD;
        pot[i] = pot[i - 1] * BAZA % MOD;
    }

    h_[0] = s[s.size() - 1];
    for(int i = s.size() - 2, cnt = 1; i >= 0; --i, ++cnt)
        h_[cnt] = (h_[cnt - 1] * BAZA + s[i]) % MOD;
}

ll calc(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h[x - 1] * pot[y] % MOD;
    return ((((ll)h[x + y - 1] - k) % MOD) + MOD) % MOD;
}

ll calc_(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h_[x - 1] * pot[y] % MOD;
    return ((((ll)h_[x + y - 1] - k) % MOD) + MOD) % MOD;
}

int cntDec[MAXN];
ll decrease[MAXN];
ll increase[MAXN], letInc[MAXN][30];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0),

    cin >> s;

    calcHash();
    ll sol = 0;

    int len = s.size();

    REP(i, len){
        //neparni
        ll lo = 1, hi = min(i + 1, len - i);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }

            if(calc(i, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        cntDec[i - lo + 1] ++;
        cntDec[i + 1] -= 2;
        cntDec[i + lo + 1] ++;

        sol += lo;
        increase[i] += lo;

        ll jump = lo + 1;
        lo = 0, hi = min(i + 1, len - i) - jump;
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }
            if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        letInc[i + jump - 1][s[i - jump + 1] - 'a'] += lo + 1;
        letInc[i - jump + 1][s[i + jump - 1] - 'a'] += lo + 1;

        if(i == len - 1) continue;
        //neparni
        lo = 0, hi = min(i + 1, len - i - 1);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
                assert(s.size() == 0);
            }
            if(calc(i + 1, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        sol += lo;

        if(lo){
            cntDec[i - lo + 1] ++;
            cntDec[i + 1] --;
            cntDec[i + 2] --;
            cntDec[i + lo + 2] ++;
        }

        jump = lo + 1;
        lo = 0, hi = min(i + 1, len - i - 1) - jump;
        while(lo < hi){

            ll mid = (lo + hi + 1) >> 1;
            if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }
            if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        letInc[i + jump][s[i - jump + 1] - 'a'] += lo + 1;
        letInc[i - jump + 1][s[i + jump] - 'a'] += lo + 1;
    }

    ll cnt = 0, curr = 0;

    REP(i, len){
        cnt += cntDec[i];
        curr += cnt;
        decrease[i] = curr;
    }

    ll best = 0;
    REP(i, len)
        REP(j, 26){
            best = max(best, increase[i] + letInc[i][j] - decrease[i]);

        }

    cout << sol + best;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:64:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
                ~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:64:65: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
                                           ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:85:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:85:79: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:102:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
                ~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:102:69: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
                                               ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:125:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
palinilap.cpp:125:83: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 0 / 46