oj.uz

Submission #161939

# Submission time Handle Problem Language Result Execution time Memory
161939 2019-11-05T11:12:40 Z shayan_p Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 4092 KB 
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=2e6+10,mod=1e9+7;
const ll inf=1e18;

int f[maxn];
char ss[maxn], s[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int q; cin>>q;
    while(q--){
	cin>>ss;
	int N=strlen(ss);
	int n=0;
	for(int i=0;i<=N-1-i;i++){
	    if(i==N-1-i) s[n++]=ss[i];
	    else s[n++]=ss[i], s[n++]='+', s[n++]=ss[N-1-i], s[n++]='+';
	}
	if(s[n-1] =='+') --n;
	
	int L=-1,R=-1;
	for(int i=0;i<n;i++){
	    if(i<R){
		L=R=i;
		while(L>0 && R<n-1 && s[L-1]==s[R+1]) L--,R++;
		f[i]=R-i;
	    }
	    else{
		if(i + f[L+R-i] >= R){
		    f[i]= R-i;
		    L=i-f[i];
		    while(L>0 && R<n-1 && s[L-1]==s[R+1]) L--,R++;
		    f[i]=R-i;
		}
		else{
		    f[i]= f[L+R-i];
		}		
	    }
	}
	int ans=0;
	int nw=0;
	while(nw<n){
	    int pt=nw+2;
	    while(pt<n && 2*f[(nw+pt)>>1]<pt-nw) pt+=4;
	    if(pt<n){
		ans+=2;
		nw=pt+2;
	    }
	    else{
		ans++;
		break;
	    }
	}
	cout<<ans<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 667 ms 516 KB Output is correct
11 Correct 52 ms 504 KB Output is correct
12 Correct 16 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 667 ms 516 KB Output is correct
11 Correct 52 ms 504 KB Output is correct
12 Correct 16 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Execution timed out 10095 ms 4092 KB Time limit exceeded
15 Halted 0 ms 0 KB -