oj.uz

Submission #448822

# Submission time Handle Problem Language Result Execution time Memory
448822 2021-08-01T23:53:57 Z osmanallazov Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 312 ms 40380 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAKS=1e6+10;
ll v1[MAKS],v2[MAKS],hash1[MAKS],hash2[MAKS];
ll p1=37,p2=101;
pair<ll,ll>subhash(int i, int j){
	return make_pair(hash1[i] - (j ? hash1[j - 1] * v1[i - j + 1] : 0),
					 hash2[i] - (j ? hash2[j - 1] * v2[i - j + 1] : 0));
}
string s;
int n;
void re(){
	cin>>s;
	n=s.length();
	hash1[0]=hash2[0]=s[0];
	for(int i=1;i<n;i++){
		hash1[i]=hash1[i-1]*p1+s[i];
		hash2[i]=hash2[i-1]*p2+s[i];
	}
}
int main(){
    v1[0]=v2[0]=1;
	for(int i=1;i<MAKS;i++){
		v1[i]=v1[i-1]*p1;
		v2[i]=v2[i-1]*p2;
	}
    int T;
    cin>>T;
    while(T--){
        re();
		int ans=0;
		int e=0,d=n-1;
		for(int i=0;i<n/2;i++){
			if(subhash(i,e)==subhash(d,n-i-1)){
				e=i+1;
				d=n-i-2;
				ans+=2;
			}
		}
		if(s.length()%2 || e<n/2)ans++;
		cout<<ans<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15940 KB Output is correct
2 Correct 8 ms 15856 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Correct 8 ms 15852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15940 KB Output is correct
2 Correct 8 ms 15856 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Correct 8 ms 15852 KB Output is correct
6 Correct 8 ms 15860 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 8 ms 15936 KB Output is correct
9 Correct 8 ms 15940 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15940 KB Output is correct
2 Correct 8 ms 15856 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Correct 8 ms 15852 KB Output is correct
6 Correct 8 ms 15860 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 8 ms 15936 KB Output is correct
9 Correct 8 ms 15940 KB Output is correct
10 Correct 10 ms 16228 KB Output is correct
11 Correct 9 ms 16204 KB Output is correct
12 Correct 10 ms 16232 KB Output is correct
13 Correct 10 ms 16100 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15940 KB Output is correct
2 Correct 8 ms 15856 KB Output is correct
3 Correct 8 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Correct 8 ms 15852 KB Output is correct
6 Correct 8 ms 15860 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 8 ms 15936 KB Output is correct
9 Correct 8 ms 15940 KB Output is correct
10 Correct 10 ms 16228 KB Output is correct
11 Correct 9 ms 16204 KB Output is correct
12 Correct 10 ms 16232 KB Output is correct
13 Correct 10 ms 16100 KB Output is correct
14 Correct 312 ms 40348 KB Output is correct
15 Correct 156 ms 37772 KB Output is correct
16 Correct 269 ms 40380 KB Output is correct
17 Correct 154 ms 29916 KB Output is correct