Submission #879736

#	Time	Username	Problem	Language	Result	Execution time	Memory
879736		Phuong0703	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	167 ms	28896 KiB

palindromic

/*
    Cred : SunnyYeahBoi
    It's my last chance (⌐■_■)
    Problem :
*/

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define all(v) v.begin(), v.end()
#define endl "\n"
#define NAME "a"

const int MAXN = 1e6 + 5;
const int inf = 1e18;
const int MOD = 1e9 + 7;

void FileInput(){
    if(fopen(NAME".inp" , "r") == NULL)
        freopen(NAME".inp" , "w" , stdout);
    freopen(NAME".inp" , "r" , stdin);
    freopen(NAME".out" , "w" , stdout);
}

const int BASE = 311;

string s;
int pref[MAXN] , powBase[MAXN];

int get(int l , int r){
    return ((pref[r] - (pref[l - 1] * powBase[r - l + 1]) % MOD) % MOD + MOD) % MOD;
}

void solve(){
    cin >> s;
    int n = s.size();
    s = '*' + s;

    powBase[0] = 1;
    for(int i = 1 ; i < MAXN ; i++)
        powBase[i] = powBase[i - 1] * BASE % MOD;
    for(int i = 1 ; i < s.size() ; i++)
        pref[i] = (pref[i - 1] * BASE + (s[i] - 'a' + 1)) % MOD;
    
    int curL = 1 , curR = n , res = 0;
    while(curL <= curR){
        int len = 1;
        while(curL + len - 1 <= curR && get(curL , curL + len - 1) != get(curR - len + 1 , curR)){
            // cout << curL << " " << curR << " " << len << " " << get(curL , curL + len - 1) << " " << get(curR - len + 1 , curR) << endl;
            len++;
        }
        if(curL + len - 1 < curR - len + 1)
            res += 2;
        else res++;
        curL += len;
        curR -= len;
        // cout << curL << " " << curR << endl;
    }

    cout << res << endl;
}

int32_t main(){
    // FileInput();
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void solve()':
palindromic.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 1 ; i < s.size() ; i++)
      |                     ~~^~~~~~~~~~
palindromic.cpp: In function 'void FileInput()':
palindromic.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(NAME".inp" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen(NAME".inp" , "r" , stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen(NAME".out" , "w" , stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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