oj.uz

Submission #638961

# Submission time Handle Problem Language Result Execution time Memory
638961 2022-09-08T06:07:13 Z zaneyu Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 70 ms 28412 KB 
/*input
4
bonobo
deleted
racecar
racecars
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET(v,x) lower_bound(ALL(v),x)-v.begin()
const int maxn=1e6+3;
const int INF=0x3f3f3f3f;
const int MOD=1e6+3;
const ld PI=acos(-1.0l);
const ld eps=1e-6;
const ll INF64=9e18+1;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
int mult(int a,int b){
    return 1LL*a*b%MOD;
}
ll mypow(ll a,ll b,ll mod){
    if(b<=0) return 1;
    a%=mod;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
typedef unsigned long long ull;
ull pw[maxn],pf[maxn];
int n;
ull get(int l,int r){
    return (pf[r]-pf[l-1]*pw[r-l+1]);
}
void solve(){
    string s;
    cin>>s;
    n=sz(s);
    s="0"+s;
    REP1(i,n){
        pf[i]=pf[i-1]*31+(s[i]-'a'+1);
    }
    int i=1,j=n;
    int a=1,b=n;
    int ans=0;
    while(i<j){
        if(get(a,i)==get(j,b)){
            a=i+1,b=j-1;
            ans+=2;
        }
        ++i,--j;
    }
    if(a<=b) ++ans;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int t;
    cin>>t;
    pw[0]=1;
    REP1(i,maxn-1) pw[i]=pw[i-1]*31;
    while(t--) solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 4 ms 8136 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 5 ms 8136 KB Output is correct
6 Correct 4 ms 8156 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 4 ms 8276 KB Output is correct
11 Correct 4 ms 8272 KB Output is correct
12 Correct 4 ms 8360 KB Output is correct
13 Correct 5 ms 8328 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8132 KB Output is correct
3 Correct 4 ms 8136 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 5 ms 8136 KB Output is correct
6 Correct 4 ms 8156 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 4 ms 8276 KB Output is correct
11 Correct 4 ms 8272 KB Output is correct
12 Correct 4 ms 8360 KB Output is correct
13 Correct 5 ms 8328 KB Output is correct
14 Correct 70 ms 28412 KB Output is correct
15 Correct 44 ms 23360 KB Output is correct
16 Correct 67 ms 27508 KB Output is correct
17 Correct 42 ms 18908 KB Output is correct