oj.uz

Submission #369183

# Submission time Handle Problem Language Result Execution time Memory
369183 2021-02-20T18:34:29 Z ljuba Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 243 ms 20352 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
 
const char nl = '\n';

const int MOD = 1e9 + 7;
const int p = 31;

inline int mul(int a, int b) {
    return (a * 1LL * b) % MOD;
}

inline int add(int a, int b) {
    return (a + b) % MOD;
}

inline int sub(int a, int b) {
    return (a - b + MOD) % MOD;
}

void solve() {
    string s;
    cin >> s;
    int n = sz(s);

    int tren = p;
    vi hsh(n+1);
    for(int i = 0; i < n; ++i) {
        hsh[i+1] = add(hsh[i], mul(tren, (s[i]-'a'+1)));
        tren = mul(tren, p);
    }
    vi inv(n+1);
    inv[0] = 1;
    for(int i = 1; i <= n; ++i) {
        inv[i] = mul(inv[i-1], 129032259);
    }

    int ans = 0;
    int posl = 1;
    int posl2 = n;

    for(int i = 1; i <= n / 2; ++i) {
        int hes1 = mul(sub(hsh[i], hsh[posl-1]), inv[posl-1]);
        int hes2 = mul(sub(hsh[posl2], hsh[n-i]), inv[n-i]);
        if(hes1 == hes2) {
            ans += 2;
            posl = i + 1;
            posl2 = n - i;
        }
    }

    dbg(posl, posl2);

    ans += (posl <= posl2);

    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int testCases = 1;
    cin >> testCases;
    while(testCases--)
        solve();
 
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 388 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 388 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 2 ms 512 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 388 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 243 ms 20352 KB Output is correct
15 Correct 125 ms 14796 KB Output is correct
16 Correct 226 ms 18872 KB Output is correct
17 Correct 122 ms 11096 KB Output is correct