Submission #105499

#	Time	Username	Problem	Language	Result	Execution time	Memory
105499		JakubLap	Palinilap (COI16_palinilap)	C++14	17 / 100	352 ms	33416 KiB

palinilap

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

long long prefiks_1[100005], prefiks_2[100005], sufiks_1[100005], sufiks_2[100005], potegi_1[100005], potegi_2[100005], wynik;
long long poprawka, maks, maksy[100005], odejmowanie[100005];
pair<int, int> prefiks_palindromiczny_przod[100005], prefiks_palindromiczny_tyl[100005], sufiks_palindromiczny_przod[100005], sufiks_palindromiczny_tyl[100005];
long long dodawanie[100005][30], rozmiar = 1, ilosc_palindromow, indeks_1, indeks_2, indeks_3;
string slowo;

bool sprawdzenie_nieparzyste(int x, int i, int zmiana, int miejsce){
    if (poprawka == -1){
        long long pom_1 = sufiks_1[slowo.size() - i + x] - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
        long long pom_2 = prefiks_1[i + x + 1] - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
        long long pom_3 = sufiks_2[slowo.size() - i + x] - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
        long long pom_4 = prefiks_2[i + x + 1] - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
            return true;
    }
    else{
        long long pom_1 = sufiks_1[slowo.size() - i + x] - (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x - zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
        long long pom_2 = prefiks_1[i + x + 1] - (potegi_1[x + zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x + zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
        long long pom_3 = sufiks_2[slowo.size() - i + x] - (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x - zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
        long long pom_4 = prefiks_2[i + x + 1] - (potegi_2[x + zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x + zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (miejsce == 1){
            if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
                return true;
        }
        pom_1 = sufiks_1[slowo.size() - i + x] + (potegi_1[x + zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x + zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_1[slowo.size() - i - x - 1] * potegi_1[(x * 2 + 1)] % 1000000009;
        pom_2 = prefiks_1[i + x + 1] + (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x - zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 1)] % 1000000009;
        pom_3 = sufiks_2[slowo.size() - i + x] + (potegi_2[x + zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x + zmiana] * slowo[i + zmiana]) % 1000000009 - sufiks_2[slowo.size() - i - x - 1] * potegi_2[(x * 2 + 1)] % 1000000009;
        pom_4 = prefiks_2[i + x + 1] + (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x - zmiana] * slowo[i + zmiana]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 1)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (miejsce == 2){
            if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
                return true;
        }
    }
    return false;
}

bool sprawdzenie_parzyste(int x, int i, int zmiana, int miejsce){
    if (poprawka == -1){
        long long pom_1 = sufiks_1[slowo.size() - i + x] - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
        long long pom_2 = prefiks_1[i + x + 2] - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
        long long pom_3 = sufiks_2[slowo.size() - i + x] - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
        long long pom_4 = prefiks_2[i + x + 2] - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
            return true;
    }
    else{
        long long pom_1 = sufiks_1[slowo.size() - i + x] - (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
        long long pom_2 = prefiks_1[i + x + 2] - (potegi_1[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 + (potegi_1[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
        long long pom_3 = sufiks_2[slowo.size() - i + x] - (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
        long long pom_4 = prefiks_2[i + x + 2] - (potegi_2[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 + (potegi_2[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (miejsce == 1){
            if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
                return true;
        }
        pom_1 = sufiks_1[slowo.size() - i + x] + (potegi_1[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_1[slowo.size() - i - x - 2] * potegi_1[(x * 2 + 2)] % 1000000009;
        pom_2 = prefiks_1[i + x + 2] + (potegi_1[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_1[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_1[i - x] * potegi_1[(x * 2 + 2)] % 1000000009;
        pom_3 = sufiks_2[slowo.size() - i + x] + (potegi_2[x + zmiana + 1] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x + zmiana + 1] * slowo[i + zmiana + 1]) % 1000000009 - sufiks_2[slowo.size() - i - x - 2] * potegi_2[(x * 2 + 2)] % 1000000009;
        pom_4 = prefiks_2[i + x + 2] + (potegi_2[x - zmiana] * slowo[i - zmiana]) % 1000000009 - (potegi_2[x - zmiana] * slowo[i + zmiana + 1]) % 1000000009 - prefiks_2[i - x] * potegi_2[(x * 2 + 2)] % 1000000009;
        if (pom_1 < 0)
            pom_1 += 1000000009;
        if (pom_2 < 0)
            pom_2 += 1000000009;
        if (pom_3 < 0)
            pom_3 += 1000000009;
        if (pom_4 < 0)
            pom_4 += 1000000009;
        if (miejsce == 2){
            if (abs(pom_1 - pom_2) % 1000000009 == 0 && abs(pom_3 - pom_4) % 1000000009 == 0)
                return true;
        }
    }
    return false;
}

int bin_search_nieparzysty(int i, int zmiana, int miejsce){
    int pomocnicza = slowo.length() - 1 - i;
    int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
    if (poczatek > koniec)
        return 0;
    while(poczatek <= koniec){
        srodek = (poczatek + koniec) / 2;
        if (sprawdzenie_nieparzyste(srodek, i, zmiana, miejsce)){
            poczatek = srodek + 1;
            wynik_bin = srodek;
        }
        else
            koniec = srodek - 1;
    }
    return max(wynik_bin + 1 - zmiana, 0);
}

int bin_search_parzysty(int i, int zmiana, int miejsce){
    int pomocnicza = slowo.length() - 2 - i;
    int poczatek = zmiana, koniec = min(i, pomocnicza), srodek, wynik_bin = -1;
    if (poczatek > koniec)
        return 0;
    while(poczatek <= koniec){
        srodek = (poczatek + koniec) / 2;
        if (sprawdzenie_parzyste(srodek, i, zmiana, miejsce)){
            poczatek = srodek + 1;
            wynik_bin = srodek;
        }
        else
            koniec = srodek - 1;
    }
    return max(wynik_bin + 1 - zmiana, 0);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> slowo;
    potegi_1[0] = 1;
    potegi_2[0] = 1;
    int dlugosc = slowo.size();
    while(rozmiar < dlugosc)
        rozmiar *= 2;
    rozmiar--;
    for (int i = 1; i <= dlugosc; i++){
        potegi_1[i] = 37 * potegi_1[i - 1];
        potegi_1[i] %= 1000000009;
        potegi_2[i] = 41 * potegi_2[i - 1];
        potegi_2[i] %= 1000000009;
    }
    for (int i = 1; i <= dlugosc; i++){
        prefiks_1[i] = prefiks_1[i - 1] * 37 +  slowo[i - 1];
        prefiks_2[i] = prefiks_2[i - 1] * 41 +  slowo[i - 1];
        sufiks_1[i] = sufiks_1[i - 1] * 37 + slowo[dlugosc - i];
        sufiks_2[i] = sufiks_2[i - 1] * 41 + slowo[dlugosc - i];
        prefiks_1[i] %= 1000000009;
        prefiks_2[i] %= 1000000009;
        sufiks_1[i] %= 1000000009;
        sufiks_2[i] %= 1000000009;
    }
    for (int i = 0; i < dlugosc; i++){
        poprawka = -1;
        poprawka = bin_search_nieparzysty(i, 0, 0);
        wynik += (long long)poprawka;
        if (poprawka > 1){
            //cout << i - (poprawka - 1) << " " << i - 1 << " " << ilosc_palindromow << "\n";
            prefiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i - (poprawka - 1), i - 1);
            prefiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i - 1, i - (poprawka - 1));
            sufiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i + (poprawka - 1), i + 1);
            sufiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i + 1, i + (poprawka - 1));
            ilosc_palindromow++;
            //if (i > 53000)
                //break;
        }
        if (i - poprawka >= 0 && i + poprawka < dlugosc){
            dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] += (long long)bin_search_nieparzysty(i, poprawka, 1);
            dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] += (long long)bin_search_nieparzysty(i, poprawka, 2);
            maksy[i - poprawka] = max(maksy[i - poprawka], (long long)dodawanie[i - poprawka][slowo[i + poprawka] - 'a']);
            maksy[i + poprawka] = max((long long)dodawanie[i + poprawka][slowo[i - poprawka] - 'a'], maksy[i + poprawka]);
        }
        if (i <  dlugosc - 1){
            poprawka = -1;
            poprawka = bin_search_parzysty(i, 0, 0);
            wynik += (long long)poprawka;
            if (poprawka > 0){
                //cout << i - (poprawka - 1) << " " << i << "\n";
                prefiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i - (poprawka - 1), i);
                prefiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i, i - (poprawka - 1));
                sufiks_palindromiczny_przod[ilosc_palindromow] = make_pair(i + poprawka, i + 1);
                sufiks_palindromiczny_tyl[ilosc_palindromow] = make_pair(i + 1, i + poprawka);
                ilosc_palindromow++;
            }
            if (i - poprawka >= 0 && i + poprawka + 1 < dlugosc){
                dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] += (long long)bin_search_parzysty(i, poprawka, 1);
                dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] += (long long)bin_search_parzysty(i, poprawka, 2);
                maksy[i - poprawka] = max(maksy[i - poprawka], (long long)dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a']);
                maksy[i + poprawka + 1] = max((long long)dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'], maksy[i + poprawka + 1]);
            }
        }
         //cout << prefiks_palindromiczny_przod[0].first << " " << ilosc_palindromow << "\n";
        //cout << ilosc_palindromow << " " << i << " |\n";
    }
    //for (int i = 0; i < ilosc_palindromow; i++){
       //// if (prefiks_palindromiczny_przod[i].first == 1 && prefiks_palindromiczny_przod[i].second == 2)
            //cout << i << "\n";
    //}
    //cout << prefiks_palindromiczny_przod[0].first << "\n";
    sort(prefiks_palindromiczny_przod, prefiks_palindromiczny_przod + ilosc_palindromow);
    //cout << prefiks_palindromiczny_przod[0].first << "\n";
    sort(prefiks_palindromiczny_tyl, prefiks_palindromiczny_tyl + ilosc_palindromow);
    //cout << prefiks_palindromiczny_przod[0].first << "\n";
    indeks_1 = 0;
    indeks_3 = 0;
    long long suma = 0;
    //cout << prefiks_palindromiczny_przod[0].first << " " << prefiks_palindromiczny_przod[0].second << "\n";
    //cout << prefiks_palindromiczny_tyl[0].first << " " << prefiks_palindromiczny_tyl[0].second << "\n";
    //for (int i = 0; i < 100; i++){
     //   cout << prefiks_palindromiczny_przod[i].first << " " << prefiks_palindromiczny_przod[i].second << " #\n";
    //}
    for (int i = 0; i < dlugosc; i++){
        if (indeks_3 == ilosc_palindromow)
            break;
        while (indeks_3 < ilosc_palindromow && prefiks_palindromiczny_tyl[indeks_3].first == i - 1){
            suma -= (long long)i - prefiks_palindromiczny_tyl[indeks_3].second;
            indeks_3++;
        }
        while (indeks_1 < ilosc_palindromow && prefiks_palindromiczny_przod[indeks_1].first == i)
            indeks_1++;
        suma += (long long)indeks_1 - indeks_3;
        odejmowanie[i] = (long long)suma;
        if (i == 100)
            break;
        //cout << odejmowanie[i] << " " << prefiks_palindromiczny_tyl[indeks_3].first << " " << indeks_3 << " " << i << " $\n";
    }
    odejmowanie[dlugosc - 1] = suma;
    sort(sufiks_palindromiczny_przod, sufiks_palindromiczny_przod + ilosc_palindromow);
    sort(sufiks_palindromiczny_tyl, sufiks_palindromiczny_tyl + ilosc_palindromow);
    indeks_1 = ilosc_palindromow - 1, indeks_3 = ilosc_palindromow - 1;
    suma = 0;
    for (int i = dlugosc - 1; i >= 0; i--){
        if (indeks_3 < 0)
            break;
        while (indeks_3 >= 0 && sufiks_palindromiczny_tyl[indeks_3].first == i + 1){
            suma -= (long long)sufiks_palindromiczny_tyl[indeks_3].second - i;
            indeks_3--;
        }
        while (indeks_1 >= 0 && sufiks_palindromiczny_przod[indeks_1].first == i)
            indeks_1--;
        suma += (long long)indeks_3 - indeks_1;
        odejmowanie[i] += (long long)suma;
    }
    odejmowanie[0] += suma;
    for (int i = 0; i < dlugosc; i++){
        maks = max((long long)maksy[i] - max(odejmowanie[i], (long long)0), maks);
    }
    wynik += (long long)maks;
    cout << wynik;
}

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