답안 #105500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105500 2019-04-12T20:00:02 Z JakubLap Palinilap (COI16_palinilap) C++14
100 / 100
500 ms 36732 KB
#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[200005], prefiks_palindromiczny_tyl[200005], sufiks_palindromiczny_przod[200005], sufiks_palindromiczny_tyl[200005];
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){
    //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){
        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){
            //cout << pom_1 << " " << pom_2 << " " << i << " " << x << "\n";
            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;
        //cout << pom_1 << " " << pom_2 << " ";
        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){
            //cout << pom_1 << " " << pom_2 << " " << i << " " << x << "\n";
            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){
            //cout << i - zmiana << " " << i + zmiana + 1 << " " << i << " #\n";
            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;
        //cout << srodek << " 1\n";
        //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 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;
        //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 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];
        //cout << sufiks[i] << " " << sufiks[i] % 1000000009 << "\n";
        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;
        //cout << poprawka << "\n";
        if (poprawka > 1){
            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));
            //cout << i - (poprawka - 1) << " " << i - 1 << " " << poprawka << "\n";
        }
        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);
            //if (i - poprawka == 40){
            //    cout << dodawanie[i - poprawka][int(slowo[i + poprawka] - 'a')] << " " << slowo[i + poprawka] << " " << bin_search_nieparzysty(i, poprawka, 1) << " " << poprawka << " " << i << " 1\n";
            //}
            //if (i + poprawka == 40){
            //    cout << dodawanie[i + poprawka][int(slowo[i - poprawka] - 'a')] << " " << slowo[i - poprawka] << " " << bin_search_nieparzysty(i, poprawka, 2) << " " << poprawka << " " << i << " 2\n";
            //}
            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]);
            //cout << dodawanie[i - poprawka][slowo[i + poprawka]] << " " << dodawanie[i + poprawka][slowo[i - poprawka]] << " " << i << " " << poprawka << " 1\n";
        }
        //cout << poprawka << " 1\n";
        if (i <  dlugosc - 1){
            poprawka = -1;
            poprawka = bin_search_parzysty(i, 0, 0);
            //cout << poprawka << " 2\n";
            wynik += (long long)poprawka;
            if (poprawka > 0){
                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);
                //cout << i - (poprawka - 1) << " " << i << "\n";
                //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'] += (long long)bin_search_parzysty(i, poprawka, 1);
                dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] += (long long)bin_search_parzysty(i, poprawka, 2);
                //if (i - poprawka == 40){
                //    cout << dodawanie[i - poprawka][slowo[i + poprawka + 1] - 'a'] << " " << slowo[i + poprawka + 1] << " " << bin_search_parzysty(i, poprawka, 1) << " " << poprawka << " " << i << " 3\n";
                //}
                //if (i + poprawka == 40){
                 //   cout << dodawanie[i + poprawka + 1][slowo[i - poprawka] - 'a'] << " " << slowo[i - poprawka] << " " << bin_search_parzysty(i, poprawka, 2) << " " << poprawka << " " << i << " 4\n";
                //}
                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 << dodawanie[i - poprawka][slowo[i + poprawka + 1]] << " " << dodawanie[i + poprawka + 1][slowo[i - poprawka]] << " " << i << " " << poprawka << " 2\n";
            }
        }
    }
    sort(prefiks_palindromiczny_przod, prefiks_palindromiczny_przod + ilosc_palindromow);
    sort(prefiks_palindromiczny_tyl, prefiks_palindromiczny_tyl + ilosc_palindromow);
    indeks_1 = 0;
    indeks_3 = 0;
    long long suma = 0;
    //for (int i = 0; i < dlugosc; i++){
        //cout << slowo[i] << " " << i << "\n";
    //}
    //cout << ilosc_palindromow << " " << slowo[40] << "\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;
        //cout << odejmowanie[i] << " " << preiks_palindromiczny_przod[indeks_1].first << " " << prefiks_palindromiczny_tyl[indeks_3].first << " " << i << " " << indeks_1 << " " << indeks_3 << "\n";
    }
    while (indeks_3 < ilosc_palindromow && prefiks_palindromiczny_tyl[indeks_3].first ==  dlugosc - 1){
        suma -= (long long)dlugosc - prefiks_palindromiczny_tyl[indeks_3].second;
        indeks_3++;
    }
    odejmowanie[dlugosc - 1] = suma;
    //cout << odejmowanie[dlugosc - 1] << "\n";
    //cout << odejmowanie[49994] << "\n";
    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;
        //cout << suma << " " << sufiks_palindromiczny_przod[indeks_1].first << " " << sufiks_palindromiczny_tyl[indeks_3].first << " " << i << " " << indeks_1 << " " << indeks_3 << "\n";
    }
    while (indeks_3 >= 0 && sufiks_palindromiczny_tyl[indeks_3].first == 0){
        suma -= (long long)sufiks_palindromiczny_tyl[indeks_3].second + 1;
        indeks_3--;
    }
    odejmowanie[0] += suma;
    //cout << odejmowanie[49994] << "\n";
    long long op = 0, ops = -1;
    for (int i = 0; i < dlugosc; i++){
        if (ops > odejmowanie[i]){
            ops = odejmowanie[i];
            op = i;
        }
        //cout << maksy[i] - odejmowanie[i] << " " << odejmowanie[i] << " " << maksy[i] << " " << i << "\n";
        maks = max((long long)maksy[i] - max(odejmowanie[i], (long long)0), maks);
    }
    wynik += (long long)maks;
    cout << wynik;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:301:15: warning: variable 'op' set but not used [-Wunused-but-set-variable]
     long long op = 0, ops = -1;
               ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2176 KB Output is correct
2 Correct 9 ms 2176 KB Output is correct
3 Correct 16 ms 2048 KB Output is correct
4 Correct 12 ms 1536 KB Output is correct
5 Correct 11 ms 1792 KB Output is correct
6 Correct 16 ms 2048 KB Output is correct
7 Correct 13 ms 1920 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 33532 KB Output is correct
2 Correct 184 ms 36600 KB Output is correct
3 Correct 263 ms 36624 KB Output is correct
4 Correct 433 ms 32504 KB Output is correct
5 Correct 322 ms 32656 KB Output is correct
6 Correct 348 ms 32452 KB Output is correct
7 Correct 392 ms 32664 KB Output is correct
8 Correct 119 ms 12380 KB Output is correct
9 Correct 348 ms 32512 KB Output is correct
10 Correct 414 ms 32608 KB Output is correct
11 Correct 189 ms 36600 KB Output is correct
12 Correct 500 ms 36728 KB Output is correct
13 Correct 410 ms 33676 KB Output is correct
14 Correct 393 ms 32460 KB Output is correct
15 Correct 361 ms 32572 KB Output is correct
16 Correct 340 ms 36732 KB Output is correct
17 Correct 330 ms 30712 KB Output is correct
18 Correct 316 ms 32600 KB Output is correct
19 Correct 293 ms 30712 KB Output is correct