Submission #850375

#	Time	Username	Problem	Language	Result	Execution time	Memory
850375		Benmath	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1513 ms	28040 KiB

palindromic

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

int n;
long long int prefiksnihash[1000001];
long long int stepen[1000001];
long long int stependvice[35];
long long int prost_stependvice[35];
long long int mod= 1e9 + 9;
long long int prost= 67;

long long int inv (long long int x, long long int y){
    long long int step = 1e9 + 8 - y;
    long long int ans = 1;
    for(int j = 31; j>=0; j--){
        if(step >= stependvice[j]){
            step = step - stependvice[j];
            ans = (ans * prost_stependvice[j]) % mod;
        }
    }
    return ans;
}


long long int podijeli(long long int a, long long int b , long long int y){
    long long int rezultat = (a * inv(b,y)) % mod;
    return rezultat;
}


long long int calculate(int i, int j){
    if(i > j){
        swap(i,j);
    }
    if(i == 0){
        return prefiksnihash[j];
    }else{
        long long int rezultat = (prefiksnihash[j] - prefiksnihash[i-1] + mod)%mod;
        return podijeli (rezultat, stepen[i], i);
        
    }
}

int main()
{
    stepen[0] = 1;
    stependvice[0] = 1;
    for(int i = 1; i<=31; i++){
        stependvice[i] = (stependvice[i-1] * 2);
    }
    prost_stependvice[0] = prost;
    for(int i = 1; i<=31; i++){
        prost_stependvice[i] = (prost_stependvice[i-1] * prost_stependvice[i-1]) % mod;
    }
    for(int i = 1; i<=1000000; i++){
        stepen[i] = (stepen[i-1] * prost) %mod;
    }
    
    int t;
    cin >> t;
    while (t--){
        string s;
        cin >> s;
        n = s.size();
        for(int i = 0; i < n; i++){
            long long int vrijednostslova = s[i] - 'a' + 1;
            if (i == 0){
                prefiksnihash[i] = vrijednostslova;
            }else {
                prefiksnihash[i] = (prefiksnihash[i-1] + vrijednostslova * stepen[i]) % mod;
            }
        }
        
        int odgovor = 0;
        int t1 = 0;
        int l = 0;
        int r = n-1;
        //cout << calculate(0,1) << " " << calculate(4,5)<<endl;
        while (t1 == 0){
            int check = 0;
            int intervalprvi = -1;
            int intervaldrugi = -1;
            for (int i = l; i <= r; i++){
                if (check > 0){
                    break;
                }
                int prvi1 = l;
                int prvi2 = i;
                int drugi2 = r;
                int drugi1 = r - (i - l);
                if (prvi2 < drugi1){
                    if (calculate(prvi1,prvi2) == calculate(drugi1,drugi2)){
                        odgovor = odgovor + 2;
                        intervalprvi = prvi2 + 1;
                        intervaldrugi = drugi1 - 1;
                        check ++;
                        break;
                    }
                }
            }
            if (check == 0){
                odgovor = odgovor + 1;
                break;
            }
            if (intervalprvi > intervaldrugi){
                break;
            }
            l = intervalprvi;
            r = intervaldrugi;
        }
        cout << odgovor << endl;
    }
    
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40