Cod sursa(job #3268913)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 18 ianuarie 2025 01:42:10
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.55 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const char BOGUS = '*';


string withBogus(const string& s) {
    const int n = s.length();
    
    // Construct string of size n filled with null characters
    // Predefined sizes are usually faster, because they don't require
    // more allocations.
    string sp(2 * n - 1, '\0');

    for (int i = 0; i < n; i++) {
        sp[2 * i] = s[i];
        if (i < n - 1) {
            sp[2 * i + 1] = BOGUS;
        }
    }

    return sp;
}


void extendRadius(const string& sp, int center, int& radius) {
    while (center - (radius + 1) >= 0 &&
           center + (radius + 1) >= 0 &&
           sp[center - (radius + 1)] == sp[center + (radius + 1)]) {
        radius++;
    }
}


vector<int> computePalindromeRadii(const string& sp) {
    const int n = sp.length();

    vector<int> result(n);
    int center = 0, radius = 0;
    int oldCenter, oldRadius;

    while (center < n) {
        extendRadius(sp, center, radius);
        
        result[center] = radius;
        oldCenter = center;
        oldRadius = radius;

        center++;
        radius = 0;

        while (center <= oldCenter + oldRadius) {
            /*
             *  We have this example "abcacbad" -> "a*b*c*a*c*b*a*d" after adding
             *   bogus characters.
             *                _
             *  ||a * b * c *|a|* c * b * a | * d
             *  ||        ^   |   |  ____ └-|---oldCenter + oldRadius    
             *  ||<-┬---->|   |   └-|center||  
             *  |   |     |   └-oldCenter   | 
             *  |   |  ┌--┘                 |  
             *  |   └--|-maxMirroredRadius  |  
             *  |      └--┐                 |  
             *  |         |                 |  
             *  |         |                 |  
             *  | mirroredCenter            |  
             *  |                           |
             *  |<--     old sequence    -->|
             */
            const int mirroredCenter = oldCenter - (center - oldCenter);
            const int maxMirroredRadius = oldCenter + oldRadius - center;

            if (result[mirroredCenter] != maxMirroredRadius) {
                result[center] = min(result[mirroredCenter], maxMirroredRadius);
                center++;
            } else if (result[mirroredCenter] == maxMirroredRadius) {
                result[center] = maxMirroredRadius;
                radius = maxMirroredRadius;
                break;
            }
        }
    }
    return result;
}


int64_t computeResult(const string& s) {
    string sp = withBogus(s);
    const int n = sp.length();

    auto radii = computePalindromeRadii(sp);

    int64_t result = 0;

    for (int i = 0; i < n; i++) {
        /* result[i] is the radius, where we remove the bogus chars,
         * so (result[i] / 2) for the real radius -> 
         * -> real radius * 2 = length
         *
         * special case for even length palindromic sequences ->
         * -> we remove the bogus character from the middle;
         */
        int length;
        const bool isOddLength = i % 2 == 0;
        if (isOddLength) {
            length = (radii[i] / 2 * 2) + 1;
        } else {
            length = radii[i] + 1;
        }

        result += length / 2 + isOddLength;
    }

    return result;    
}

int main() {
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");

    string s;
    f >> s;

    g << computeResult(s) << std::endl;

    return 0;
}