Submission #104904

# Submission time Handle Problem Language Result Execution time Memory
104904 2019-04-09T15:02:56 Z JakubLap Palinilap (COI16_palinilap) C++11
0 / 100
155 ms 14700 KB
#include <bits/stdc++.h>
using namespace std;

long long prefiks[100005], sufiks[100005], potegi[100005], wynik;
int poprawka, dodawanie[100005][30], maks;
string slowo;

bool sprawdzenie_nieparzyste(int x, int i, int zmiana, int miejsce){
    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){
    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){
            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){
            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;
    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 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;
    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 wynik_bin + 1 - zmiana;
}

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

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rozmiar < slowo.size())
            ~~~~~~~~^~~~~~~~~~~~~~
palinilap.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i <= slowo.size(); i++){
                     ~~^~~~~~~~~~~~~~~
palinilap.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i <= slowo.size(); i++){
                     ~~^~~~~~~~~~~~~~~
palinilap.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < slowo.size(); i++){
                     ~~^~~~~~~~~~~~~~
palinilap.cpp:98:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i - poprawka >= 0 && i + poprawka < slowo.size()){
                                  ~~~~~~~~~~~~~^~~~~~~~~~~~~~
palinilap.cpp:99:56: warning: array subscript has type 'char' [-Wchar-subscripts]
             dodawanie[i - poprawka][slowo[i + poprawka]] += bin_search_nieparzysty(i, poprawka, 1);
                                                        ^
palinilap.cpp:100:56: warning: array subscript has type 'char' [-Wchar-subscripts]
             dodawanie[i + poprawka][slowo[i - poprawka]] += bin_search_nieparzysty(i, poprawka, 2);
                                                        ^
palinilap.cpp:101:77: warning: array subscript has type 'char' [-Wchar-subscripts]
             maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka]], dodawanie[i + poprawka][slowo[i - poprawka]]));
                                                                             ^
palinilap.cpp:101:123: warning: array subscript has type 'char' [-Wchar-subscripts]
             maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka]], dodawanie[i + poprawka][slowo[i - poprawka]]));
                                                                                                                           ^
palinilap.cpp:103:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i <  slowo.size() - 1){
             ~~^~~~~~~~~~~~~~~~~~~
palinilap.cpp:107:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i - poprawka >= 0 && i + poprawka < slowo.size()){
                                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~
palinilap.cpp:108:64: warning: array subscript has type 'char' [-Wchar-subscripts]
                 dodawanie[i - poprawka][slowo[i + poprawka + 1]] += bin_search_parzysty(i, poprawka, 1);
                                                                ^
palinilap.cpp:109:64: warning: array subscript has type 'char' [-Wchar-subscripts]
                 dodawanie[i + poprawka + 1][slowo[i - poprawka]] += bin_search_parzysty(i, poprawka, 2);
                                                                ^
palinilap.cpp:110:85: warning: array subscript has type 'char' [-Wchar-subscripts]
                 maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1]], dodawanie[i + poprawka + 1][slowo[i - poprawka]]));
                                                                                     ^
palinilap.cpp:110:135: warning: array subscript has type 'char' [-Wchar-subscripts]
                 maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1]], dodawanie[i + poprawka + 1][slowo[i - poprawka]]));
                                                                                                                                       ^
palinilap.cpp:113:77: warning: array subscript has type 'char' [-Wchar-subscripts]
         maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1]], dodawanie[i + poprawka + 1][slowo[i - poprawka]]));
                                                                             ^
palinilap.cpp:113:127: warning: array subscript has type 'char' [-Wchar-subscripts]
         maks = max(maks, max(dodawanie[i - poprawka][slowo[i + poprawka + 1]], dodawanie[i + poprawka + 1][slowo[i - poprawka]]));
                                                                                                                               ^
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 14700 KB Output isn't correct
2 Halted 0 ms 0 KB -