Submission #619708

#	Time	Username	Problem	Language	Result	Execution time	Memory
619708		socpite	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	438 ms	22740 KiB

palindromic

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

#define f first
#define s second

typedef long long ll;

const int maxn = 1e6+5;
const int mod = 1e9+7;

int t, n, q;

string str, str2;

int d[2*maxn];
int man1[maxn], man2[maxn];

void pp(){
    string tmp;
    for(int i = n-1; i >= n/2 + (n&1); i--)tmp+=str[i];
    str2 = tmp;
    tmp = "";
    for(int i = 0; i < n/2; i++)tmp+=str[i];
    str = tmp;
    tmp = "$#";
    for(int i = 0; i < n/2; i++){
        tmp+=str[i];
        tmp+='#';
    }
    tmp+='^';
    str = tmp;
    tmp = "$#";
    for(int i = n/2+(n&1); i < n; i++){
        tmp+=str2[i-(n/2+(n&1))];
        tmp+='#';
    }
    tmp += '^';
    str2 = tmp;
    //cout << str << " " << str2 << endl;
}

int main(){
    cin >> t;
    while(t--){
        cin >> str;
        n=str.size();
        pp();
        for(int i = 1, l =0,r = 0; i < str.size(); i++){
            if(r < i)d[i]=0;
            else d[i] = min(r-i, d[l+r-i]);
            while(str[i+d[i]] == str2[i-d[i]] && str[i-d[i]] == str2[i+d[i]])d[i]++;
            if(i+d[i] > r){
                l = i-d[i], r = i+d[i];
            }
            if(i&1){
                if(i > 1 && i < str.size()-2)man2[(i>>1)-1]=d[i]>>1;
            }
            else{
                if(i && i < str.size()-1)man1[(i>>1)-1]=d[i]>>1;
            }
        }
        int crr = 0, ans = 0;
        for(int i = 0; i < n/2; i++){
            if(man1[i]){
                if(crr >= i-man1[i]+1 && crr <= i){
                    crr+=(i-crr)*2+1;
                    ans+=2;
                }
            }
            //cout << man1[i] << endl;
            if(man2[i] && i < n/2-1){
                if(crr >= i-man2[i]+1 && crr <= i){
                    crr+=(i-crr+1)*2;
                    ans+=2;
                }
            }
            //cout << man2[i] << endl;
        }
        if(crr < n/2 || (n&1))ans++;
        cout << ans << "\n";
    }

}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:49:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i = 1, l =0,r = 0; i < str.size(); i++){
      |                                    ~~^~~~~~~~~~~~
palindromic.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(i > 1 && i < str.size()-2)man2[(i>>1)-1]=d[i]>>1;
      |                             ~~^~~~~~~~~~~~~~
palindromic.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 if(i && i < str.size()-1)man1[(i>>1)-1]=d[i]>>1;
      |                         ~~^~~~~~~~~~~~~~

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