oj.uz

Submission #1095037

# Submission time Handle Problem Language Result Execution time Memory
1095037 2024-10-01T07:51:33 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
0 / 100
 0 ms 600 KB 
#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;
  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;
    poww[0] = 1;
    fr(i, 1, n) poww[i] = poww[i - 1] * base % mod;
    ll l = 1, r = n, cnt = 0;
    while(true) {
      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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -