oj.uz

Submission #1108809

# Submission time Handle Problem Language Result Execution time Memory
1108809 2024-11-05T07:01:31 Z koukirocks Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 159 ms 28292 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

ll pw(ll a,ll b) {
    ll ans=1;
    ll now=a;
    while (b) {
        if (b&1) {
            ans*=now;
            ans%=P;
        }
        now*=now;
        now%=P;
        b>>=1;
    }
    return ans;
}

struct Hash {
    string s;
    ll n;
    ll x;
    vector<ll> pre,inv;
    Hash(string _s,int x):s(_s),n(s.size()-1),x(x) {
        pre.resize(n+1);
        inv.resize(n+1);
        ll now=1;
        inv[0]=1;
        inv[1]=pw(x,P-2);
        for (int i=1;i<=n;i++) {
            now = (now*x)%P;
            inv[i]=inv[i-1]*inv[1];
            inv[i]%=P;
            pre[i]=pre[i-1]+s[i]*now;
            pre[i]%=P;
        }
    }
    ll query(ll a,ll b) {
        return (pre[b]-pre[a-1]+P)%P*inv[a-1]%P;
    }
};

void solve() {
    string s;
    cin>>s;
    int n = s.size();
    s = '-'+s;
    Hash h(s,83);
    int now=1;
    int ans=0;
    for (int i=1;2*i<=n;i++) {
        if (h.query(now,i)==h.query(n-i+1,n-now+1)) {
            ans+=2;
            now=i+1;
        }
    }
    cout<<ans+(now<=n-now+1)<<"\n";
}

int main() {
    speed;
    int t;
    cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 3 ms 708 KB Output is correct
13 Correct 3 ms 680 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 3 ms 708 KB Output is correct
13 Correct 3 ms 680 KB Output is correct
14 Correct 158 ms 28292 KB Output is correct
15 Correct 99 ms 22936 KB Output is correct
16 Correct 159 ms 27156 KB Output is correct
17 Correct 103 ms 15248 KB Output is correct