oj.uz

Submission #397431

# Submission time Handle Problem Language Result Execution time Memory
397431 2021-05-02T07:35:04 Z Nicholas_Patrick Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 440 ms 37344 KB 
#include <iostream>
#include <queue>
#include <array>
#include <string>
using namespace std;

const int hus=3;
const int mod[]={0x3fffffdd, 0x3fffffd7, 0x3fffffad};
const int base=123;
using hash_t=array<int, hus>;
hash_t powers[1000001];
void getPowers(){
	for(int i=hus; i--;)
		powers[0][i]=1;
	for(int i=0; i<1000000; i++){
		for(int j=hus; j--;)
			powers[i+1][j]=(long long)powers[i][j]*base%mod[j];
	}
}
vector<hash_t> getHash(string& s){
	int n=s.size();
	vector<hash_t> ret(n+1);
	for(int i=hus; i--;)
		ret[0][i]=0;
	for(int i=0; i<n; i++){
		for(int j=hus; j--;)
			ret[i+1][j]=(ret[i][j]+(long long)powers[i][j]*s[i])%mod[j];
	}
	return ret;
}
bool match(vector<hash_t>& s, int sl, int sr, vector<hash_t>& t, int tl, int tr){
	if(sl<tl){
		for(int i=hus; i--;){
			if(((long long)(s[sr][i]-s[sl][i])*powers[tl-sl][i]-t[tr][i]+t[tl][i])%mod[i])
				return false;
		}
		return true;
	}else if(sl>tl){
		for(int i=hus; i--;){
			if(((long long)(t[tr][i]-t[tl][i])*powers[sl-tl][i]-s[sr][i]+s[sl][i])%mod[i])
				return false;
		}
		return true;
	}else{
		for(int i=hus; i--;){
			if((s[sr][i]-s[sl][i]-t[tr][i]+t[tl][i])%mod[i])
				return false;
		}
		return true;
	}
}
int solve(string& s){
	int n=s.size();
	auto rec=getHash(s);
	int ret=0;
	int l=0, r=n;
	for(int i=1; l<r; i++){
		if(match(rec, l, i, rec, r-(i-l), r)){
			ret+=2;
			r-=i-l;
			l=i;
		}
	}
	if(r<l)
		ret--;
	return ret;
}
int main(){
	getPowers();
	int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		cout<<solve(s)<<endl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11980 KB Output is correct
2 Correct 14 ms 12048 KB Output is correct
3 Correct 14 ms 11992 KB Output is correct
4 Correct 14 ms 12040 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11980 KB Output is correct
2 Correct 14 ms 12048 KB Output is correct
3 Correct 14 ms 11992 KB Output is correct
4 Correct 14 ms 12040 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 14 ms 11952 KB Output is correct
7 Correct 14 ms 11980 KB Output is correct
8 Correct 16 ms 12048 KB Output is correct
9 Correct 16 ms 12040 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11980 KB Output is correct
2 Correct 14 ms 12048 KB Output is correct
3 Correct 14 ms 11992 KB Output is correct
4 Correct 14 ms 12040 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 14 ms 11952 KB Output is correct
7 Correct 14 ms 11980 KB Output is correct
8 Correct 16 ms 12048 KB Output is correct
9 Correct 16 ms 12040 KB Output is correct
10 Correct 20 ms 12300 KB Output is correct
11 Correct 17 ms 12236 KB Output is correct
12 Correct 18 ms 12272 KB Output is correct
13 Correct 18 ms 12236 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11980 KB Output is correct
2 Correct 14 ms 12048 KB Output is correct
3 Correct 14 ms 11992 KB Output is correct
4 Correct 14 ms 12040 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 14 ms 11952 KB Output is correct
7 Correct 14 ms 11980 KB Output is correct
8 Correct 16 ms 12048 KB Output is correct
9 Correct 16 ms 12040 KB Output is correct
10 Correct 20 ms 12300 KB Output is correct
11 Correct 17 ms 12236 KB Output is correct
12 Correct 18 ms 12272 KB Output is correct
13 Correct 18 ms 12236 KB Output is correct
14 Correct 440 ms 37344 KB Output is correct
15 Correct 245 ms 32720 KB Output is correct
16 Correct 383 ms 34528 KB Output is correct
17 Correct 241 ms 24904 KB Output is correct