oj.uz

Submission #693677

# Submission time Handle Problem Language Result Execution time Memory
693677 2023-02-03T06:50:38 Z PoPularPlusPlus Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 2907 ms 36436 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

ll store[1000002];
ll store1[1000002];

const int P = 31;

ll add(ll x, ll y){
	return (x+y)%mod;
}

ll multi(ll x , ll y){
	return (x*y)%mod;
}

ll power(ll x , ll y){
	if(x == P && y <= 1000000 && store1[y] != -1)return store1[y];
	x %= mod;
	ll res = 1;
	while(y > 0){
		if(y&1)res=multi(res,x);
		y=y>>1;
		x = multi(x,x);
	}
	if(x == P && y <= 1000000)store1[y] = res;
	return res;
}

ll inv(ll n){
	if(n <= 1000000 && store[n] != -1)return store[n];
	if(n <= 1000000)return store[n] = power(n,mod-2);
	return power(n,mod-2);
}

void solve(){
	memset(store,-1,sizeof store);
	memset(store1,-1,sizeof store1);
	int n;
	string s;
	cin >> s;
	n = s.size();
	string a , b;
	a = "";
	b = "";
	for(int i = 0; i < n/2; i++)a += s[i];
	for(int i = (n + 1)/2; i < n; i++)b += s[i];
	int N = a.size();
	ll hash[N];
	ll hash1[N];
	for(int i = 0; i < N; i++){
		hash[i] = multi(power(P,i),a[i]-'a');
		if(i)hash[i] = add(hash[i],hash[i-1]);
		hash1[i] = multi(power(P,i),b[i]-'a');
		if(i)hash1[i] = add(hash1[i],hash1[i-1]);
	}
	int ans = 0;
	int i = 0;
	for(int j = 0; j < N; j++){
			ll x = hash[j] - (i > 0 ? hash[i-1] : 0);
			x += mod;
			x %= mod;
			x = multi(x , inv(power(P,i)));
			ll y = hash1[N-(i+1)];
			if(j < N - 1){
				y -= hash1[N-(j+2)];
				y += mod;
				y %= mod;
			}
			y = multi(y,inv(power(P,N-(j + 1))));
			//cout << i << ' ' << j << ' ' <<  x << ' ' << y << '\n';
			if(x == y){
				ans += 2;
				i = j + 1;
			}
		}
		if(n % 2 || i != N)ans++;
		cout << ans << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15944 KB Output is correct
2 Correct 21 ms 15944 KB Output is correct
3 Correct 13 ms 15924 KB Output is correct
4 Correct 21 ms 15956 KB Output is correct
5 Correct 21 ms 15956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15944 KB Output is correct
2 Correct 21 ms 15944 KB Output is correct
3 Correct 13 ms 15924 KB Output is correct
4 Correct 21 ms 15956 KB Output is correct
5 Correct 21 ms 15956 KB Output is correct
6 Correct 22 ms 15988 KB Output is correct
7 Correct 18 ms 15956 KB Output is correct
8 Correct 25 ms 15956 KB Output is correct
9 Correct 22 ms 15972 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15944 KB Output is correct
2 Correct 21 ms 15944 KB Output is correct
3 Correct 13 ms 15924 KB Output is correct
4 Correct 21 ms 15956 KB Output is correct
5 Correct 21 ms 15956 KB Output is correct
6 Correct 22 ms 15988 KB Output is correct
7 Correct 18 ms 15956 KB Output is correct
8 Correct 25 ms 15956 KB Output is correct
9 Correct 22 ms 15972 KB Output is correct
10 Correct 49 ms 16196 KB Output is correct
11 Correct 26 ms 16084 KB Output is correct
12 Correct 45 ms 16084 KB Output is correct
13 Correct 43 ms 16152 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15944 KB Output is correct
2 Correct 21 ms 15944 KB Output is correct
3 Correct 13 ms 15924 KB Output is correct
4 Correct 21 ms 15956 KB Output is correct
5 Correct 21 ms 15956 KB Output is correct
6 Correct 22 ms 15988 KB Output is correct
7 Correct 18 ms 15956 KB Output is correct
8 Correct 25 ms 15956 KB Output is correct
9 Correct 22 ms 15972 KB Output is correct
10 Correct 49 ms 16196 KB Output is correct
11 Correct 26 ms 16084 KB Output is correct
12 Correct 45 ms 16084 KB Output is correct
13 Correct 43 ms 16152 KB Output is correct
14 Correct 2844 ms 36340 KB Output is correct
15 Correct 1304 ms 31680 KB Output is correct
16 Correct 2907 ms 36436 KB Output is correct
17 Correct 1662 ms 26896 KB Output is correct