제출 #479255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479255		Mike4235	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	13 ms	15948 KiB

palindromic

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

void add(int& a, int b, int mod) {
    if ((a += b) >= mod) a -= mod;
}

int mul(int a, int b, int mod) {
    return a * b % MOD;
}

string s;
int t, n;
int p1[1000005], p2[1000005];

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    p1[1] = 1; p2[1] = 1;
    for1(i,2,1000000) {
        p1[i] = p1[i - 1] * 29 % MOD;
        p2[i] = p2[i - 1] * 31 % MOD2;
    }

    cin >> t;
    while (t--) {
        cin >> s;
        n = sz(s);
        s = ' ' + s;

        int c1 = 0, c2 = 0, c3 = 0, c4 = 0, res = 0, st = 0;
        for1(i,1,n / 2) {
            add(c1, mul(s[i] - 'a' + 1, p1[i - st], MOD), MOD);
            add(c2, mul(s[i] - 'a' + 1, p2[i - st], MOD2), MOD2);
            c3 = mul(c3, 29, MOD); add(c3, s[n - i + 1] - 'a' + 1, MOD);
            c4 = mul(c4, 31, MOD2); add(c4, s[n - i + 1] - 'a' + 1, MOD2);

            if (c1 == c3 && c2 == c4) {
                res += 2;
                c1 = 0; c2 = 0; c3 = 0; c4 = 0; st = i;
            }
        }

        cout << res + (c1 > 0 || n & 1) << "\n";
    }
    
}

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