Submission #105107

#	Time	Username	Problem	Language	Result	Execution time	Memory
105107		JakubLap	Palinilap (COI16_palinilap)	C++14	0 / 100	260 ms	17016 KiB

palinilap

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

long long prefiks[100005], sufiks[100005], potegi[100005], wynik;
int poprawka, dodawanie[100005][30], maks, drzewo[270005], aktualizacje[270005], rozmiar = 1, maksy[100005];
string slowo;

void aktualizuj_pozniej(int x){
    drzewo[x * 2] += aktualizacje[x];
    drzewo[x * 2 + 1] += aktualizacje[x];
    aktualizacje[x * 2] += aktualizacje[x];
    aktualizacje[x * 2 + 1] += aktualizacje[x];
    aktualizacje[x] = 0;
}

int znajdz(int p, int k, int a, int b, int x){
    if (p > b || k < a)
        return 0;
    if (p <= a && k >= b)
        return drzewo[x];
    aktualizuj_pozniej(x);
    int max_l = znajdz(p, k, a, (a + b) / 2, x * 2);
    int max_p = znajdz(p, k, (a + b) / 2 + 1, b, x * 2 + 1);
    drzewo[x] = max(drzewo[x * 2], drzewo[x * 2 + 1]);
    return max(max_l, max_p);
}

void aktualizuj(int p, int k, int a, int b, int x, int w){
    if (p > b || k < a)
        return;
    if (p <= a && k >= b){
        //cout << a << " " << b << "\n";
        drzewo[x] += w;
        aktualizacje[x] += w;
        return;
    }
    aktualizuj_pozniej(x);
    aktualizuj(p, k, a, (a + b) / 2, x * 2, w);
    aktualizuj(p, k, (a + b) / 2 + 1, b, x * 2 + 1, w);
    drzewo[x] = max(drzewo[x * 2], drzewo[x * 2 + 1]);
}

bool sprawdzenie_nieparzyste(int x, int i, int zmiana, int miejsce){
    //cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 << " " << potegi[(x * 2 + 1)] << " " << sufiks[slowo.size() - i + x] << " " << sufiks[slowo.size() - i - x - 1] << " " << i << " " << x << "\n";
    //cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] << " " << prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] << " " << x << "\n";
    if (poprawka == -1){
        if (sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
            return true;
    }
    else{
        if (miejsce == 1){
            if (sufiks[slowo.size() - i + x] - (potegi[x - zmiana] * slowo[i - zmiana]) + (potegi[x - zmiana] * slowo[i + zmiana]) - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] - (potegi[x + zmiana] * slowo[i - zmiana]) + (potegi[x + zmiana] * slowo[i + zmiana]) - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
                return true;
        }
        if (miejsce == 2){
            if (sufiks[slowo.size() - i + x] + (potegi[x + zmiana] * slowo[i - zmiana]) - (potegi[x + zmiana] * slowo[i + zmiana]) - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 == prefiks[i + x + 1] + (potegi[x - zmiana] * slowo[i - zmiana]) - (potegi[x - zmiana] * slowo[i + zmiana]) - prefiks[i - x] * potegi[(x * 2 + 1)] % 1000000009)
                return true;
        }
    }
    return false;
}

bool sprawdzenie_parzyste(int x, int i, int zmiana, int miejsce){
    //cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] % 1000000009 << " " << potegi[(x * 2 + 1)] << " " << sufiks[slowo.size() - i + x] << " " << sufiks[slowo.size() - i - x - 1] << " " << i << " " << x << "\n";
    //cout << sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 1] * potegi[(x * 2 + 1)] << " " << prefiks[i + x + 1] - prefiks[i - x] * potegi[(x * 2 + 1)] << " " << x << "\n";
    if (poprawka == -1){
        if (sufiks[slowo.size() - i + x] - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
            return true;
    }
    else{
        if (miejsce == 1){
            //cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " $\n";
            if (sufiks[slowo.size() - i + x] - (potegi[x - zmiana] * slowo[i - zmiana]) + (potegi[x - zmiana] * slowo[i + zmiana + 1]) - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] - (potegi[x + zmiana + 1] * slowo[i - zmiana]) + (potegi[x + zmiana + 1] * slowo[i + zmiana + 1]) - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
                return true;
        }
        if (miejsce == 2){
            //cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " #\n";
            if (sufiks[slowo.size() - i + x] + (potegi[x + zmiana + 1] * slowo[i - zmiana]) - (potegi[x + zmiana + 1] * slowo[i + zmiana + 1]) - sufiks[slowo.size() - i - x - 2] * potegi[(x * 2 + 2)] % 1000000009 == prefiks[i + x + 2] + (potegi[x - zmiana] * slowo[i - zmiana]) - (potegi[x - zmiana] * slowo[i + zmiana + 1]) - prefiks[i - x] * potegi[(x * 2 + 2)] % 1000000009)
                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 (zmiana)
            //cout << srodek << " " << i << " |\n";
        if (sprawdzenie_nieparzyste(srodek, i, zmiana, miejsce)){
            //cout << zmiana << " " << srodek << "\n";
            poczatek = srodek + 1;
            wynik_bin = srodek;
        }
        else
            koniec = srodek - 1;
    }
    //cout << wynik_bin + 1 << " ";
    return wynik_bin + 1 - zmiana;
}

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;
        //cout << srodek << "\n";
        if (sprawdzenie_parzyste(srodek, i, zmiana, miejsce)){
            //cout << 1 << "\n";
            poczatek = srodek + 1;
            wynik_bin = srodek;
        }
        else
            koniec = srodek - 1;
    }
    //cout << wynik_bin + 1 << " ";
    return wynik_bin + 1 - zmiana;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> slowo;
    potegi[0] = 1;
    int dlugosc = slowo.size();
    while(rozmiar < dlugosc)
        rozmiar *= 2;
    rozmiar--;
    for (int i = 1; i <= dlugosc; i++){
        potegi[i] = 37 * potegi[i - 1];
        potegi[i] %= 1000000009;
    }
    for (int i = 1; i <= dlugosc; i++){
        prefiks[i] = prefiks[i - 1] * 37 +  slowo[i - 1];
        sufiks[i] = sufiks[i - 1] * 37 + slowo[dlugosc - i];
        //cout << sufiks[i] << " " << sufiks[i] % 1000000009 << "\n";
        prefiks[i] %= 1000000009;
        sufiks[i] %= 1000000009;
    }
    for (int i = 0; i < dlugosc; i++){
        poprawka = -1;
        poprawka = bin_search_nieparzysty(i, 0, 0);
        wynik += poprawka;
        if (poprawka > 1){
            aktualizuj(i - (poprawka - 1), i - 1, 0, rozmiar, 1, 1);
            aktualizuj(i + 1, i + (poprawka - 1), 0, rozmiar, 1, 1);
            //cout << znajdz(i - (poprawka - 1), i + (poprawka - 1), 0, rozmiar, 1) << "\n";
        }
        if (i - poprawka >= 0 && i + poprawka < dlugosc){
            dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 1);
            dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] += bin_search_nieparzysty(i, poprawka, 2);
            maksy[i - poprawka] = max(maksy[i - poprawka], dodawanie[i - poprawka][slowo[i + poprawka] - 'a']);
            maksy[i + poprawka] = max(dodawanie[i + poprawka][slowo[i - poprawka] - 'a'], maksy[i - poprawka]);
            //cout << dodawanie[i - poprawka][slowo[i + poprawka]] << " " << dodawanie[i + poprawka][slowo[i - poprawka]] << " " << i << " 1\n";
        }
        //cout << poprawka << " 1\n";
        if (i <  dlugosc - 1){
            poprawka = -1;
            poprawka = bin_search_parzysty(i, 0, 0);
            //cout << poprawka << " 2\n";
            wynik += poprawka;
            if (poprawka > 0){
                aktualizuj(i - (poprawka - 1), i + poprawka, 0, rozmiar, 1, 1);
                //cout << znajdz(0, 0, 0, rozmiar, 1) << "\n";
                //cout << znajdz(i - (poprawka - 1), i + poprawka, 0, rozmiar, 1) << " " << i - (poprawka - 1) << " " << i + poprawka << "\n";
            }
            if (i - poprawka >= 0 && i + poprawka + 1 < dlugosc){
                dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] += bin_search_parzysty(i, poprawka, 1);
                dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] += bin_search_parzysty(i, poprawka, 2);
                maksy[i - poprawka] = max(maksy[i - poprawka], dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a']);
                maksy[i + poprawka + 1] = max(dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'], maksy[i - poprawka]);
                //cout << dodawanie[i - poprawka][slowo[i + poprawka + 1]] << " " << dodawanie[i + poprawka + 1][slowo[i - poprawka]] << " " << i << " 2\n";
            }
        }
    }
    for (int i = 0; i < dlugosc; i++){
        cout << znajdz(i, i, 0, rozmiar, 1) << "\n";
        maks = max(maksy[i] - znajdz(i, i, 0, rozmiar, 1), maks);
    }
    wynik += maks;
    cout << wynik;
}

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