Submission #1095046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095046		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	162 ms	108632 KiB

palindromic

#include <bits/stdc++.h>

#define ll long long
#define fr(i, d, c) for(ll i = d; i <= c; i++)
#define fl(i, d, c) for(ll i = d; i >= c; i--)
const int N = 1e6 + 9;
const ll base = 31, mod = 1e9 + 7;
using namespace std;
    
ll n, h[N], poww[N], pr[N];
vector<ll> pos[base];
vector<ll> ans;
string s;

ll get_hash(ll l, ll r) {
  return (h[r] - h[l - 1] * poww[r - l + 1] + mod * mod) % mod;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll t;
  cin>> t;
  poww[0] = 1;
  fr(i, 1, 1e6) poww[i] = poww[i - 1] * base % mod;
  while(t--) {
    cin >> s;
    n = s.size();
    s = ' ' + s;
    fr(i, 1, n) pos[s[i] - '0'].push_back(i);
    fr(i, 1, n) h[i] = (h[i - 1] * base + s[i] - 'a' + 1) % mod;
    ll l = 1, r = n, cnt = 0;
    while(l <= r) {
      ll dd = false;
      while(pos[s[l] - '0'].size()) {
        ll nx = pos[s[l] - '0'].back();
        pos[s[l] - '0'].pop_back();
        ll sz = r - nx + 1;
        if(l + sz - 1 >= nx) break;
        if(get_hash(l, l + sz - 1) == get_hash(nx, r)) {
          l = l + sz;
          r = nx - 1;
          cnt += 2;
          dd = true;
          break;
        }
      }
      if(!dd) {
        cnt++;
        break;
      }
    }
    cout<<cnt<<'\n';
  }
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40