oj.uz

Submission #916428

# Submission time Handle Problem Language Result Execution time Memory
916428 2024-01-25T21:28:58 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 166 ms 29540 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 42 ms 10584 KB Output is correct
2 Correct 43 ms 10588 KB Output is correct
3 Correct 22 ms 10588 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 10584 KB Output is correct
2 Correct 43 ms 10588 KB Output is correct
3 Correct 22 ms 10588 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10588 KB Output is correct
6 Correct 43 ms 10588 KB Output is correct
7 Correct 26 ms 10588 KB Output is correct
8 Correct 42 ms 10588 KB Output is correct
9 Correct 42 ms 10588 KB Output is correct
10 Correct 44 ms 11096 KB Output is correct
11 Correct 27 ms 10840 KB Output is correct
12 Correct 43 ms 10840 KB Output is correct
13 Correct 43 ms 11096 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 10584 KB Output is correct
2 Correct 43 ms 10588 KB Output is correct
3 Correct 22 ms 10588 KB Output is correct
4 Correct 42 ms 10584 KB Output is correct
5 Correct 42 ms 10588 KB Output is correct
6 Correct 43 ms 10588 KB Output is correct
7 Correct 26 ms 10588 KB Output is correct
8 Correct 42 ms 10588 KB Output is correct
9 Correct 42 ms 10588 KB Output is correct
10 Correct 44 ms 11096 KB Output is correct
11 Correct 27 ms 10840 KB Output is correct
12 Correct 43 ms 10840 KB Output is correct
13 Correct 43 ms 11096 KB Output is correct
14 Correct 166 ms 29540 KB Output is correct
15 Correct 90 ms 24448 KB Output is correct
16 Correct 155 ms 28496 KB Output is correct
17 Correct 112 ms 21620 KB Output is correct