oj.uz

Submission #945413

# Submission time Handle Problem Language Result Execution time Memory
945413 2024-03-13T18:23:12 Z amirhoseinfar1385 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 95 ms 16264 KB 
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn=1000000+10;
bool check(long long a){
	for(long long i=2;i*i<=a;i++){
		if(a%i==0){
			return 0;
		}
	}
	return 1;
}

long long getav(long long a){
	while(check(a)==0){
		a++;
	}
	return a;
}
long long mod=getav(rng()%100000000+993847562),base=getav(rng()%200+1000),mp[maxn];

void aval(){
	mp[0]=1;
	for(long long i=1;i<maxn;i++){
		mp[i]=1ll*mp[i-1]*base%mod;
	}
}

void solve(){
	string s;
	cin>>s;
	long long n=s.size();
	long long mid=n/2;
	string first,second;
	for(long long i=0;i<mid;i++){
		first.push_back(s[i]);
	}
	for(long long i=mid+(n&1);i<n;i++){
		second.push_back(s[i]);
	}
	long long i=0,j=(long long)second.size()-1;
	long long res=0;
	long long hash1=0,hash2=0;
	long long last=0;
	for(long long asd=0;asd<(long long)first.size();asd++){
		hash1+=mp[i-last]*first[i];
		hash2=hash2*base+second[j];
		hash1%=mod;
		hash2%=mod;
		//cout<<asd<<" "<<first[i]<<" "<<second[j]<<" "<<hash1<<" "<<hash2<<endl;
		if(hash1==hash2){
			res+=2;
			hash1=hash2=0;
			last=i+1;
		}
		i++;
		j--;
	}
	if(hash1!=0||(n&1)){
		res++;
	}
	cout<<res<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	aval();
	long long t;
	cin>>t;
	for(long long asd=0;asd<t;asd++){
		solve();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 8 ms 8280 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 8 ms 8280 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8072 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 8 ms 8280 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8072 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 8 ms 8284 KB Output is correct
11 Correct 8 ms 8308 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 7 ms 8280 KB Output is correct
3 Correct 8 ms 8280 KB Output is correct
4 Correct 7 ms 8284 KB Output is correct
5 Correct 7 ms 8072 KB Output is correct
6 Correct 8 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 7 ms 8284 KB Output is correct
10 Correct 8 ms 8284 KB Output is correct
11 Correct 8 ms 8308 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 9 ms 8284 KB Output is correct
14 Correct 95 ms 16044 KB Output is correct
15 Correct 53 ms 13512 KB Output is correct
16 Correct 86 ms 16264 KB Output is correct
17 Correct 50 ms 12760 KB Output is correct