oj.uz

Submission #916429

# Submission time Handle Problem Language Result Execution time Memory
916429 2024-01-25T21:29:51 Z amin_2008 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 165 ms 19840 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// author: amin_2008

typedef long long ll;

#define pb push_back
#define ins insert
#define ts to_string
#define sz(x) (int)(x).size()
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define lb lower_bound
#define ub upper_bound
#define ld long double
#define endl '\n'
#define int ll

using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
using pii = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vpii = vector<pii>;
using vb = vector<bool>;
using vc = vector<char>;
using vvi = vector<vi>;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x) cerr << (#x) << ": " << x << endl

const int MOD = 998244353;
const int mod = 1e9 + 7;
const int inf = 1e18;
const int sz = 1e6 + 5;
const int N = 1e3;
const int lg = 18;
const int P = 31;

int a[sz];
int pw[sz];
int h[sz];

int get_hash(int l, int r)
{
    return (h[r + 1] - (h[l] * pw[r - l + 1]) % mod + mod) % mod;
}

void solve()
{
    pw[0] = 1;
    for(int i = 1; i < sz; i++) pw[i] = ( pw[i - 1] * P ) % mod;
    string s;
    cin >> s;
    int n = sz(s);
    h[0] = 1;
    for(int i = 0; i < n; i++) h[i + 1] = ( ( h[i] * P ) % mod + s[i] ) % mod;
    int res = 1;
    for(int i = 0; i < ( n >> 1 ); i++)
    {
        int j = i;
        int l = n - i - 1;
        int r = n - i - 1;
        for(; j < ( n >> 1 ); j++, l--)
        {
            if ( get_hash(i, j) == get_hash(l, r) )
            {
                res += 2;
                if ( !( n % 2 ) and j == ( n >> 1 ) - 1 ) res--;
                break;
            }
        }
        i = j;
    }
    cout << res << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //precompute();
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10584 KB Output is correct
2 Correct 43 ms 10584 KB Output is correct
3 Correct 22 ms 10584 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10584 KB Output is correct
2 Correct 43 ms 10584 KB Output is correct
3 Correct 22 ms 10584 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10704 KB Output is correct
6 Correct 42 ms 10584 KB Output is correct
7 Correct 27 ms 10588 KB Output is correct
8 Correct 43 ms 10732 KB Output is correct
9 Correct 43 ms 10588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10584 KB Output is correct
2 Correct 43 ms 10584 KB Output is correct
3 Correct 22 ms 10584 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10704 KB Output is correct
6 Correct 42 ms 10584 KB Output is correct
7 Correct 27 ms 10588 KB Output is correct
8 Correct 43 ms 10732 KB Output is correct
9 Correct 43 ms 10588 KB Output is correct
10 Correct 43 ms 10824 KB Output is correct
11 Correct 27 ms 10828 KB Output is correct
12 Correct 43 ms 10836 KB Output is correct
13 Correct 43 ms 10588 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10584 KB Output is correct
2 Correct 43 ms 10584 KB Output is correct
3 Correct 22 ms 10584 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10704 KB Output is correct
6 Correct 42 ms 10584 KB Output is correct
7 Correct 27 ms 10588 KB Output is correct
8 Correct 43 ms 10732 KB Output is correct
9 Correct 43 ms 10588 KB Output is correct
10 Correct 43 ms 10824 KB Output is correct
11 Correct 27 ms 10828 KB Output is correct
12 Correct 43 ms 10836 KB Output is correct
13 Correct 43 ms 10588 KB Output is correct
14 Correct 165 ms 19820 KB Output is correct
15 Correct 89 ms 19748 KB Output is correct
16 Correct 152 ms 19840 KB Output is correct
17 Correct 108 ms 16484 KB Output is correct