oj.uz

Submission #161015

# Submission time Handle Problem Language Result Execution time Memory
161015 2019-10-31T08:12:50 Z nvmdava Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 63 ms 15996 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 1000002
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

int MOD1 = 1000000007;
int MOD2 = 1000000009;
int p = 31;

string s;

int h1[N], h2[N];

int po1[N], rpo1[N];
int po2[N], rpo2[N];

int binpow(int a, int b, int m){
	int s = 1;
	while(b){
		if(b & 1)
			s = 1LL * s * a % m;
		b >>= 1;
		a = 1LL * a * a % m;
	}
	return s;
}

pair<int, int> get(int l, int r){
	pair<int, int> res;
	res.ff = 1LL * (h1[r] - h1[l - 1]) * rpo1[l] % MOD1;
	res.ss = 1LL * (h2[r] - h2[l - 1]) * rpo2[l] % MOD2;
	if(res.ss < 0)
		res.ss += MOD2;
	if(res.ff < 0)
		res.ff += MOD1;
	return res;
}

void go(){
	cin>>s;
	int n = s.size();
	for(int i = 1; i <= n; i++){
		h1[i] = (h1[i - 1] + 1LL * po1[i] * (s[i - 1] - 'a' + 1)) % MOD1;
		h2[i] = (h2[i - 1] + 1LL * po2[i] * (s[i - 1] - 'a' + 1)) % MOD2;
	}

	int l = 1, r = n;
	int ans = 0;

	for(int i = 1; i <= (l + r) / 2; i++){
		if(get(l, i) == get(r - (i - l), r)){
			ans += 2;
			// cout<<l<<' '<<i<<' '<<r - (i - l)<<' '<<r<<'\n';
			r = r - (i - l) - 1;
			l = i + 1;
			if(l == r)
				break;
		}
	}

	if(l <= r)
		++ans;

	cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
	h1[0] = 1;
	h2[0] = 1;
	po1[1] = po2[1] = rpo1[1] = rpo2[1] = 1;
	
	int rp1, rp2;
	
	rp1 = binpow(p, MOD1 - 2, MOD1);
	rp2 = binpow(p, MOD2 - 2, MOD2);

	for(int i = 2; i < N; i++){
		po1[i] = 1LL * po1[i - 1] * p % MOD1;
		po2[i] = 1LL * po2[i - 1] * p % MOD2;
		rpo1[i] = 1LL * rpo1[i - 1] * rp1 % MOD1;
		rpo2[i] = 1LL * rpo2[i - 1] * rp2 % MOD2;
	}

	cin>>t;
    while(t--){
    	go();
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15996 KB Output is correct
2 Correct 62 ms 15992 KB Output is correct
3 Incorrect 61 ms 15992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15996 KB Output is correct
2 Correct 62 ms 15992 KB Output is correct
3 Incorrect 61 ms 15992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15996 KB Output is correct
2 Correct 62 ms 15992 KB Output is correct
3 Incorrect 61 ms 15992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15996 KB Output is correct
2 Correct 62 ms 15992 KB Output is correct
3 Incorrect 61 ms 15992 KB Output isn't correct
4 Halted 0 ms 0 KB -