Submission #1095076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095076		sasde	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	100 ms	19556 KiB

palindromic

#include<bits/stdc++.h>

#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back//khi dùng pair
#define emb emplace_back//k pair
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+3;
int n,ans,base=31;
string s;
long long f[N],c[N];
int  kc(int i,int j){
    return ((1LL*f[j]-1LL*f[i-1]*c[j-i+1])%mod+mod)%mod;
}
void solve(){
    ans=0;
    cin >> s;
    n=s.size();
    s=" "+s;
    int r=1,l=n;
    for(int i=1;i<=n;++i)f[i]=(f[i-1]*base+s[i]-'a'+1)%mod;
    for(int i=1,j=n;i<j;++i,--j){
        if(kc(r,i)==kc(j,l)){
            // cout <<r<<" "<<i<<" "<<j<<" "<<l<<'\n';
            r=i+1;l=j-1;
            ans+=2;

        }
    }
    if(r<=l)++ans;
    cout << ans;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    c[0]=1;
    for(int i=1;i<=N-5;++i)c[i]=(c[i-1]*base)%mod;
    int t=1;
   cin >> t;
while(t--){
    solve();
    cout<<'\n';
}

}

Compilation message (stderr)

palindromic.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      | ^~~~

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