Submission #1245421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245421		timeflew	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	33 ms	3252 KiB

palindromic

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

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

#ifdef debug
#define dbg(...) cerr<<#__VA_ARGS__<<" = ", de(__VA_ARGS__)
template<typename T>
void de(T t) {cerr<<t<<endl;}
template<typename T, typename ...U>
void de(T t, U...u) {cerr<<t<<", ", de(u...);}
#else
#define dbg(...)
#define endl "\n"
#endif

void usaco(string s) {
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

// struct HASH {//1-based
//     const int mod=1e9+7, mod1=1e9+9, b=37, b1=39;
//     vector<ll> p, p1, h, h1;
//     HASH(string s) {
//         s=' '+s;
//         int sz=s.size();
//         p.resize(sz+1);
//         p1.resize(sz+1);
//         h.resize(sz+1);
//         h1.resize(sz+1);
//         p[0]=1;
//         p1[0]=1;
//         for(int i=1; i<=sz; i++) p[i]=p[i-1]*b%mod;
//         for(int i=1; i<=sz; i++) p1[i]=p1[i-1]*b1%mod1;
//         for(int i=1; i<=sz; i++) {
//             h[i]=(h[i-1]*b+(s[i]-'a'+1))%mod;
//             h1[i]=(h1[i-1]*b1+(s[i]-'a'+1))%mod1;
//         }    
//     }
//     pair<ll, ll> get(int l, int r) {
//         ll val=((h[r]-h[l-1]*p[r-l+1])%mod+mod)%mod, val1=((h1[r]-h1[l-1]*p1[r-l+1])%mod1+mod1)%mod1;
//         return {val, val1};
//     }
// };

void solve() {
    string s; cin>>s;
    int n=s.size();
    int l=0, r=n-1;
    ll ans=0, val=0, val1=0, base=37, g=1, mod=1e9+7;
    while(l<r) {
        val=(s[l]-'a'+val*base)%mod;
        val1=((s[r]-'a')*g+val1)%mod;
        g=g*base%mod;
        if(val==val1) {
            g=1;
            ans+=2;
            val=0, val1=0;
        }
        l++, r--;
    }
    if(n&1||(g!=1&&n%2==0)) ans++;
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}
//rating below 2700 must be solved orzorzorz

Compilation message (stderr)

palindromic.cpp: In function 'void usaco(std::string)':
palindromic.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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