oj.uz

Submission #1095046

# Submission time Handle Problem Language Result Execution time Memory
1095046 2024-10-01T07:55:24 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 162 ms 108632 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;
  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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8280 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8280 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 11 ms 9168 KB Output is correct
11 Correct 9 ms 8812 KB Output is correct
12 Correct 9 ms 8992 KB Output is correct
13 Correct 8 ms 8760 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8284 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 8 ms 8284 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 7 ms 8284 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 8 ms 8280 KB Output is correct
9 Correct 8 ms 8284 KB Output is correct
10 Correct 11 ms 9168 KB Output is correct
11 Correct 9 ms 8812 KB Output is correct
12 Correct 9 ms 8992 KB Output is correct
13 Correct 8 ms 8760 KB Output is correct
14 Correct 162 ms 82932 KB Output is correct
15 Correct 110 ms 65724 KB Output is correct
16 Correct 158 ms 108632 KB Output is correct
17 Correct 102 ms 40636 KB Output is correct