oj.uz

답안 #113914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113914 2019-05-29T08:05:35 Z ckodser Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 301 ms 55092 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

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 39552 KB Output is correct
2 Correct 98 ms 39544 KB Output is correct
3 Correct 62 ms 39592 KB Output is correct
4 Correct 99 ms 39544 KB Output is correct
5 Correct 97 ms 39544 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 39552 KB Output is correct
2 Correct 98 ms 39544 KB Output is correct
3 Correct 62 ms 39592 KB Output is correct
4 Correct 99 ms 39544 KB Output is correct
5 Correct 97 ms 39544 KB Output is correct
6 Correct 97 ms 39544 KB Output is correct
7 Correct 74 ms 39544 KB Output is correct
8 Correct 101 ms 39544 KB Output is correct
9 Correct 96 ms 39552 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 39552 KB Output is correct
2 Correct 98 ms 39544 KB Output is correct
3 Correct 62 ms 39592 KB Output is correct
4 Correct 99 ms 39544 KB Output is correct
5 Correct 97 ms 39544 KB Output is correct
6 Correct 97 ms 39544 KB Output is correct
7 Correct 74 ms 39544 KB Output is correct
8 Correct 101 ms 39544 KB Output is correct
9 Correct 96 ms 39552 KB Output is correct
10 Correct 99 ms 39688 KB Output is correct
11 Correct 73 ms 39644 KB Output is correct
12 Correct 99 ms 39648 KB Output is correct
13 Correct 103 ms 39644 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 39552 KB Output is correct
2 Correct 98 ms 39544 KB Output is correct
3 Correct 62 ms 39592 KB Output is correct
4 Correct 99 ms 39544 KB Output is correct
5 Correct 97 ms 39544 KB Output is correct
6 Correct 97 ms 39544 KB Output is correct
7 Correct 74 ms 39544 KB Output is correct
8 Correct 101 ms 39544 KB Output is correct
9 Correct 96 ms 39552 KB Output is correct
10 Correct 99 ms 39688 KB Output is correct
11 Correct 73 ms 39644 KB Output is correct
12 Correct 99 ms 39648 KB Output is correct
13 Correct 103 ms 39644 KB Output is correct
14 Correct 301 ms 53924 KB Output is correct
15 Correct 200 ms 54588 KB Output is correct
16 Correct 300 ms 55092 KB Output is correct
17 Correct 225 ms 49240 KB Output is correct