Submission #319713

#	Time	Username	Problem	Language	Result	Execution time	Memory
319713		erfanmir	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	290 ms	50264 KiB

palindromic

// In the name of god

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 1e6 + 10;
const int MAXLG = 18;
const int MOD[2] = {1000 * 1000 * 1000 + 7, 998244353};
const ll INF = 8e18;
char ch[MAXN];
int n;
ll hsh[2][MAXN], tav[2][MAXN], a[MAXN];
ll ans;

void preprocess(){
    tav[0][0] = 1;
    tav[1][0] = 1;
    for(int i = 1; i < MAXN; i++){
        tav[0][i] = 26 * tav[0][i - 1] % MOD[0];
        tav[1][i] = 26 * tav[1][i - 1] % MOD[1];
    }
}

ll get(int l, int r, int ind){
    ll res = hsh[ind][r];
    ll kam = (hsh[ind][l - 1] * tav[ind][r - l + 1]) % MOD[ind];
    res -= kam;
    res += MOD[ind];
    res %= MOD[ind];
    return res;
}

int main()
{
    preprocess();
    int t;
    scanf("%d", &t);
    while(t--){
        ans = 0;
        memset(hsh, 0, sizeof hsh);
        memset(a, 0, sizeof a);
        memset(ch, 0, sizeof ch);
        scanf("%s", ch);
        n = strlen(ch);
        for(int i = 1; i <= n; i++){
            a[i] = ch[i - 1] - 'a';
        }
        for(int i = 1; i <= n; i++){
            hsh[0][i] = 26 * hsh[0][i - 1] + a[i];
            hsh[1][i] = 26 * hsh[1][i - 1] + a[i];
            hsh[0][i] %= MOD[0];
            hsh[1][i] %= MOD[1];
        }
        int l = 1, r = n;
        for(int i = 1; l + i - 1 < r - i + 1; i++){
            ll x1, x2, y1, y2;
            x1 = get(l, l + i - 1, 0);
            x2 = get(l, l + i - 1, 1);
            y1 = get(r - i + 1, r, 0);
            y2 = get(r - i + 1, r, 1);
            if(x1 == y1 && x2 == y2){
                ans += 2;
                l = l + i;
                r = r - i;
                i = 0;
            }
        }
        if(l <= r){
            ans++;
        }
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
palindromic.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%s", ch);
      |         ~~~~~^~~~~~~~~~

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