oj.uz

Submission #113913

# Submission time Handle Problem Language Result Execution time Memory
113913 2019-05-29T08:04:47 Z ckodser Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 51512 KB 
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e6+500;
const ll inf=1e9+900;
const ll base=373;
ll tav[maxn];


ll h[maxn];
string globs;
void make_hash(string s){
    globs=s;
    ll n=s.size();
    h[0]=s[0];
    for(ll i=1;i<n;i++){
	h[i]=(h[i-1]*base+s[i])%mod;
    }
}
inline ll ok(ll a){
    if(a>=mod)return a-mod;
    return a;
}
ll find_hash(ll l,ll r){
    if(l==0)return h[r];
    return ok(h[r]-(h[l-1]*tav[r-l+1])%mod+mod);
}
bool is_equal(ll l,ll r,ll L,ll R){
    bool ans=1;
    for(ll i=0;i<r-l+1;i++){
	if(globs[l+i]!=globs[L+i]){
	    ans=0;
	}
    }
    return ans;
    return (find_hash(l,r)==find_hash(L,R));
}

ll dp[maxn];
ll maxT[maxn];
ll minT[maxn];
ll kia[maxn];
ll solve(string s){
    ll n=s.size();
    make_hash(s);
    memset(maxT,0,sizeof maxT);
    memset(dp,0,sizeof dp);
    memset(minT,0,sizeof minT);
    memset(kia,63,sizeof kia);

    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    maxT[l]=0;
	}
	else{
	    maxT[l]=0;
	    ll res=min(r-l,maxT[l+1]+2);
	    while(res>0 && !is_equal(l,l+res-1,r-res+1,r)){
		res--;
	    }
	    maxT[l]=res;
	}
    }	
    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    minT[l]=1;//set kia?
	}
	if(maxT[l]*2<=r-l+1){
	    ll last=maxT[l]+l;
	    ll v=kia[last];
	    if(v!=kia[maxn-1]){
		minT[l]=v;
	    }else{
		minT[l]=maxT[l];
		if(minT[l]==0){
		    minT[l]=r-l+1;
		}
	    }
	}else{
	    ll t=maxT[l]*2-(r-l+1);
	    minT[l]=minT[(n-t)/2];
	}
	kia[minT[l]+l]=min(kia[minT[l]+l],minT[l]);
    }
    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    dp[l]=1;
	}
	else{
	    if(minT[l]==r-l+1){
		dp[l]=1;
	    }else{
		dp[l]=2+dp[l+minT[l]];
	    }
	}
//	cout<<l<<' '<<r<<":"<<minT[l]<<' '<<maxT[l]<<' '<<dp[l]<<endl;

    }
    return dp[0];
}

int main(){
    tav[0]=1;
    for(ll i=1;i<maxn;i++){
	tav[i]=(tav[i-1]*base)%mod;
    }

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    while(t--){
	string s;
	cin>>s;
	cout<<solve(s)<<endl;
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 39544 KB Output is correct
2 Correct 97 ms 39552 KB Output is correct
3 Correct 64 ms 39544 KB Output is correct
4 Correct 96 ms 39544 KB Output is correct
5 Correct 100 ms 39544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 39544 KB Output is correct
2 Correct 97 ms 39552 KB Output is correct
3 Correct 64 ms 39544 KB Output is correct
4 Correct 96 ms 39544 KB Output is correct
5 Correct 100 ms 39544 KB Output is correct
6 Correct 97 ms 39548 KB Output is correct
7 Correct 69 ms 39516 KB Output is correct
8 Correct 94 ms 39544 KB Output is correct
9 Correct 98 ms 39544 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 39544 KB Output is correct
2 Correct 97 ms 39552 KB Output is correct
3 Correct 64 ms 39544 KB Output is correct
4 Correct 96 ms 39544 KB Output is correct
5 Correct 100 ms 39544 KB Output is correct
6 Correct 97 ms 39548 KB Output is correct
7 Correct 69 ms 39516 KB Output is correct
8 Correct 94 ms 39544 KB Output is correct
9 Correct 98 ms 39544 KB Output is correct
10 Correct 254 ms 39800 KB Output is correct
11 Correct 105 ms 39800 KB Output is correct
12 Correct 253 ms 39680 KB Output is correct
13 Correct 160 ms 39720 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 39544 KB Output is correct
2 Correct 97 ms 39552 KB Output is correct
3 Correct 64 ms 39544 KB Output is correct
4 Correct 96 ms 39544 KB Output is correct
5 Correct 100 ms 39544 KB Output is correct
6 Correct 97 ms 39548 KB Output is correct
7 Correct 69 ms 39516 KB Output is correct
8 Correct 94 ms 39544 KB Output is correct
9 Correct 98 ms 39544 KB Output is correct
10 Correct 254 ms 39800 KB Output is correct
11 Correct 105 ms 39800 KB Output is correct
12 Correct 253 ms 39680 KB Output is correct
13 Correct 160 ms 39720 KB Output is correct
14 Execution timed out 10050 ms 51512 KB Time limit exceeded
15 Halted 0 ms 0 KB -