oj.uz

Submission #161942

# Submission time Handle Problem Language Result Execution time Memory
161942 2019-11-05T11:18:31 Z shayan_p Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 10000 ms 5036 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(){
    int q; cin>>q;
    getchar();
    while(q--){
	int N=0;
	do{
	    ss[N++]=getchar();
	}while(ss[N-1]!='\n');
	ss[--N]='\0';
	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 376 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 364 KB Output is correct
5 Correct 2 ms 400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 364 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 364 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 733 ms 652 KB Output is correct
11 Correct 51 ms 504 KB Output is correct
12 Correct 17 ms 504 KB Output is correct
13 Correct 5 ms 500 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 364 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 733 ms 652 KB Output is correct
11 Correct 51 ms 504 KB Output is correct
12 Correct 17 ms 504 KB Output is correct
13 Correct 5 ms 500 KB Output is correct
14 Execution timed out 10063 ms 5036 KB Time limit exceeded
15 Halted 0 ms 0 KB -