oj.uz

Submission #525070

# Submission time Handle Problem Language Result Execution time Memory
525070 2022-02-10T15:46:33 Z Yazan_Alattar Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 578 ms 43212 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct Hash1 {
  ll SEED = 131,MOD = 1e9 + 7;
  vector<ll> ha;
  vector<ll> power;

  void build(string x) {
	power.resize(x.size());
	ha.resize(x.size());
    power[0] = 1;
    for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
    ha[0] = x[0];
    for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
  }
  
  ll get(int i, int j) {
    ll ret = ha[j];
    if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
};

struct Hash2 {
  ll SEED = 101,MOD = 1e9 + 9;
  vector<ll> ha;
  vector<ll> power;

  void build(string x) {
	power.resize(x.size());
	ha.resize(x.size());
    power[0] = 1;
    for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
    ha[0] = x[0];
    for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
  }
  
  ll get(int i, int j) {
    ll ret = ha[j];
    if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
    ret = (ret % MOD + MOD) % MOD;
    return ret;
  }
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--){
		string s;
		cin >> s;
		Hash1 Hs1; Hs1.build(s);
		Hash2 Hs2; Hs2.build(s);
		int n = s.size(), st = 0, ans = 0;
		for(int i = 0; i < n / 2; ++i){
			if(Hs1.get(st, i) == Hs1.get(n - i - 1, n - st - 1) && Hs2.get(st, i) == Hs2.get(n - i - 1, n - st - 1)){
				ans += 2;
				st = i + 1;
			}
		}
		if(n % 2 || st != n / 2) ++ans;
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 6 ms 720 KB Output is correct
11 Correct 4 ms 692 KB Output is correct
12 Correct 6 ms 732 KB Output is correct
13 Correct 5 ms 652 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 6 ms 720 KB Output is correct
11 Correct 4 ms 692 KB Output is correct
12 Correct 6 ms 732 KB Output is correct
13 Correct 5 ms 652 KB Output is correct
14 Correct 578 ms 43212 KB Output is correct
15 Correct 285 ms 38112 KB Output is correct
16 Correct 521 ms 40768 KB Output is correct
17 Correct 316 ms 23360 KB Output is correct