oj.uz

Submission #479257

# Submission time Handle Problem Language Result Execution time Memory
479257 2021-10-11T02:10:10 Z Mike4235 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 83 ms 19404 KB 
/*#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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15860 KB Output is correct
2 Correct 13 ms 15912 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 13 ms 15852 KB Output is correct
5 Correct 13 ms 15872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15860 KB Output is correct
2 Correct 13 ms 15912 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 13 ms 15852 KB Output is correct
5 Correct 13 ms 15872 KB Output is correct
6 Correct 15 ms 15888 KB Output is correct
7 Correct 13 ms 15948 KB Output is correct
8 Correct 13 ms 15924 KB Output is correct
9 Correct 13 ms 15948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15860 KB Output is correct
2 Correct 13 ms 15912 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 13 ms 15852 KB Output is correct
5 Correct 13 ms 15872 KB Output is correct
6 Correct 15 ms 15888 KB Output is correct
7 Correct 13 ms 15948 KB Output is correct
8 Correct 13 ms 15924 KB Output is correct
9 Correct 13 ms 15948 KB Output is correct
10 Correct 15 ms 15984 KB Output is correct
11 Correct 14 ms 15948 KB Output is correct
12 Correct 14 ms 15972 KB Output is correct
13 Correct 14 ms 15948 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15860 KB Output is correct
2 Correct 13 ms 15912 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 13 ms 15852 KB Output is correct
5 Correct 13 ms 15872 KB Output is correct
6 Correct 15 ms 15888 KB Output is correct
7 Correct 13 ms 15948 KB Output is correct
8 Correct 13 ms 15924 KB Output is correct
9 Correct 13 ms 15948 KB Output is correct
10 Correct 15 ms 15984 KB Output is correct
11 Correct 14 ms 15948 KB Output is correct
12 Correct 14 ms 15972 KB Output is correct
13 Correct 14 ms 15948 KB Output is correct
14 Correct 83 ms 17988 KB Output is correct
15 Correct 58 ms 18004 KB Output is correct
16 Correct 81 ms 19404 KB Output is correct
17 Correct 52 ms 17128 KB Output is correct