Submission #468964

#	Time	Username	Problem	Language	Result	Execution time	Memory
468964		wdjpng	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	314 ms	19192 KiB

palindromic

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

vector<int>powr(1e6+1);
int mod = 1e9+7;

int solve(string s)
{
    int n = s.size();

    int maxx = 1;

    int c = 0;
    int s1 = 0;
    int s2 = 0;

    rep(i,n)
    {
        if(i>=n-1-i) continue;

        s1=26*s1+s[i]-'a';
        s2+=powr[c]*(s[n-i-1]-'a');
        s1%=mod;
        s2%=mod;
        //cout<<s1<<" "<<s2<<"\n";
        c++;

        if(s1==s2)
        {
            s1=0;
            s2=0;
            c=0;

            int cur = 2*(maxx/2) + 2;
            if(i+1!=n-1-i) cur++;
            maxx = cur;
        }
    }
    return maxx;
}

signed main()
{
    int t;
    cin>>t;


    
    powr[0]=1;
    for(int i = 1; i<powr.size();i++) powr[i]=26*powr[i-1]%mod;

    while (t--)
    {
        string s;
        cin>>s;
        cout << solve(s) <<"\n";
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:57:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 1; i<powr.size();i++) powr[i]=26*powr[i-1]%mod;
      |                    ~^~~~~~~~~~~~

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