Submission #1095054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095054		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	7 ms	8284 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=1;
    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;
        }
    }
    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:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~

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