oj.uz

Submission #679867

# Submission time Handle Problem Language Result Execution time Memory
679867 2023-01-09T13:20:05 Z peijar Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 325 ms 34556 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <const int32_t MOD> struct ModInt {
  int32_t x;
  ModInt() : x(0) {}
  ModInt(long long u) : x(u % MOD) {
    if (x < 0)
      x += MOD;
  }
  friend bool operator==(const ModInt &a, const ModInt &b) {
    return a.x == b.x;
  }
  friend bool operator!=(const ModInt &a, const ModInt &b) {
    return a.x != b.x;
  }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.x < b.x; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.x > b.x; }
  friend bool operator<=(const ModInt &a, const ModInt &b) {
    return a.x <= b.x;
  }
  friend bool operator>=(const ModInt &a, const ModInt &b) {
    return a.x >= b.x;
  }
  static ModInt sign(long long k) {
    return ((k & 1) ? ModInt(MOD - 1) : ModInt(1));
  }

  ModInt &operator+=(const ModInt &m) {
    x += m.x;
    if (x >= MOD)
      x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &m) {
    x -= m.x;
    if (x < 0LL)
      x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &m) {
    x = (1LL * x * m.x) % MOD;
    return *this;
  }

  friend ModInt operator-(const ModInt &a) {
    ModInt res(a);
    if (res.x)
      res.x = MOD - res.x;
    return res;
  }
  friend ModInt operator+(const ModInt &a, const ModInt &b) {
    return ModInt(a) += ModInt(b);
  }
  friend ModInt operator-(const ModInt &a, const ModInt &b) {
    return ModInt(a) -= ModInt(b);
  }
  friend ModInt operator*(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b);
  }

  static long long fp(long long u, long long k) {
    long long res = 1LL;
    while (k > 0LL) {
      if (k & 1LL)
        res = (res * u) % MOD;
      u = (u * u) % MOD;
      k /= 2LL;
    }
    return res;
  }

  static constexpr int mod() { return MOD; }

  ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
  ModInt inv() {
    assert(x);
    return ModInt(fp(x, MOD - 2));
  }
  ModInt &operator/=(const ModInt &m) { return *this *= ModInt(m).inv(); }
  friend ModInt operator/(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b).inv();
  }

  friend ostream &operator<<(ostream &out, const ModInt &a) {
    return out << a.x;
  }
  friend istream &operator>>(istream &in, ModInt &a) { return in >> a.x; }
};

const int MOD1 = 1e9 + 9, MOD2 = 1e9 + 7;

template <typename T1, typename T2> struct ModPair {
  T1 x;
  T2 y;

  ModPair() : x(0), y(0) {}

  ModPair(int u) : x(u), y(u) {}

  ModPair(T1 _x, T2 _y) : x(_x), y(_y) {}

  ModPair &operator+=(const ModPair &other) {
    x += other.x;
    y += other.y;
    return *this;
  }

  ModPair &operator*=(const ModPair &other) {
    x *= other.x;
    y *= other.y;
    return *this;
  }

  ModPair &operator-=(const ModPair &other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }

  friend ModPair operator+(const ModPair &a, const ModPair &b) {
    return ModPair(a) += ModPair(b);
  }
  friend ModPair operator-(const ModPair &a, const ModPair &b) {
    return ModPair(a) -= ModPair(b);
  }
  friend ModPair operator*(const ModPair &a, const ModPair &b) {
    return ModPair(a) *= ModPair(b);
  }

  bool operator<(const ModPair &o) const { return pair(x, y) < pair(o.x, o.y); }
  bool operator>(const ModPair &o) const { return pair(x, y) > pair(o.x, o.y); }
  bool operator<=(const ModPair &o) const {
    return pair(x, y) <= pair(o.x, o.y);
  }
  bool operator>=(const ModPair &o) const {
    return pair(x, y) >= pair(o.x, o.y);
  }
  bool operator==(const ModPair &o) const {
    return pair(x, y) == pair(o.x, o.y);
  }

  ModPair inv() { return ModPair(x.inv(), y.inv()); };
};

using H = ModPair<ModInt<MOD1>, ModInt<MOD2>>;
const int BASE = 311;

struct Hashes {
  vector<H> po, pref, invPo;

  Hashes(string s) {
    int n = s.size();
    po.resize(n);
    invPo.resize(n);
    pref.resize(n + 1);
    po[0] = 1;
    for (int i = 1; i < n; ++i)
      po[i] = po[i - 1] * BASE;
    invPo[n - 1] = po[n - 1].inv();
    for (int i = n - 1; i > 0; --i)
      invPo[i - 1] = invPo[i] * BASE;
    for (int i = 0; i < n; ++i)
      pref[i + 1] = pref[i] + po[i] * s[i];
  }

  H getHsh(int deb, int fin) { return (pref[fin] - pref[deb]) * invPo[deb]; }
};

void solve() {
  string s;
  cin >> s;
  int N = s.size();
  if (N == 1) {
    cout << 1 << '\n';
    return;
  }
  dbg(s, N);
  Hashes hashes(s);

  int sol = 0;
  int deb = 0, fin = N;
  while (deb < fin) {
    dbg(deb, fin);
    bool found = false;
    for (int len = 1; deb + len <= fin - len; ++len)
      if (hashes.getHsh(deb, deb + len) == hashes.getHsh(fin - len, fin)) {
        found = true;
        deb += len;
        fin -= len;
        sol += 2;
        break;
      }
    if (!found) {
      sol++;
      break;
    }
  }
  cout << sol << endl;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbTests;
  cin >> nbTests;
  for (int iTest(0); iTest < nbTests; ++iTest)
    solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 3 ms 576 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 480 KB Output is correct
13 Correct 3 ms 524 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 3 ms 576 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 480 KB Output is correct
13 Correct 3 ms 524 KB Output is correct
14 Correct 325 ms 34556 KB Output is correct
15 Correct 180 ms 30372 KB Output is correct
16 Correct 286 ms 33388 KB Output is correct
17 Correct 152 ms 19248 KB Output is correct