oj.uz

답안 #161939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -