oj.uz

Submission #582975

# Submission time Handle Problem Language Result Execution time Memory
582975 2022-06-24T16:18:07 Z 600Mihnea Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 83300 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = (int) 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) {
      r = mul(r, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

int dv(int a, int b) {
  return mul(a, pw(b, M - 2));
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

const int N = (int) 1e6 + 7;
const int INF = (int) 1e9 + 7;
const int BASS = 37;
int n;
int a[N];
int dp[N];
int big[N];
int s[2][N], p[N], ip[N];

bool is_palind(int l, int r) {
  if (l > r) {
    return 1;
  }
  return a[l] == a[r] && is_palind(l + 1, r - 1);
}

int get(int type, int l, int r) {
  int sol = add(s[type][r], -s[type][l - 1]);
  return mul(sol, ip[l - 1]);
}

bool pali(int l, int r) {
  return get(0, l, r) == get(1, n + 1 - r, n + 1 - l);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  {
    p[0] = 1;
    for (int i = 1; i < N; i++) {
      p[i] = mul(p[i - 1], BASS);
    }

    ip[N - 1] = dv(1, p[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
      ip[i] = mul(ip[i + 1], BASS);
    }

  }

///  freopen ("input.txt", "r", stdin);

  int Tests;
  cin >> Tests;
  for (int tc = 1; tc <= Tests; tc++) {
    {
      string str;
      cin >> str;
      n = (int) str.size();
      int Low = 0, High = n - 1;
      for (int Step = 1; Step <= n; Step++) {
        if (Step % 2 == 0) {
          a[Step] = str[Low++] - 'a';
        } else {
          a[Step] = str[High--] - 'a';
        }
      }
    }

    for (int i = 1; i <= n; i++) {
      s[0][i] = add(s[0][i - 1], mul(p[i], a[i]));
      s[1][i] = add(s[1][i - 1], mul(p[i], a[n + 1 - i]));
    }

    for (int i = 0; i <= n + 1; i++) {
      dp[i] = -INF;
      big[i] = 0;
    }
    set<int> R;
    for (int i = 1; i <= n; i++) {
      R.insert(i);
    }
    dp[0] = 0;
    for (int i = n - 1; i >= 1; i--) {
      while (1) {
        int r;
        {
          auto it = R.lower_bound(i + 1);
          if (it == R.end()) {
            break;
          }
          r = *it;
        }
        int l = 2 * i + 1 - r;
        if (l >= 1 && is_palind(l, r)) {
          R.erase(r);
          big[r] = i;
        } else {
          break;
        }
      }
    }

    for (int r = 1; r <= n; r++) {
      if (int i = big[r]) {
        int l = 2 * i + 1 - r;
        dp[r] = max(dp[r], dp[l - 1] + 1);
      }
    }
    int sol = 2 * dp[n];
    for (int i = 0; i < n; i++) {
      sol = max(sol, 2 * dp[i] + 1);
    }
    cout << sol << "\n";
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8148 KB Output is correct
2 Correct 16 ms 8060 KB Output is correct
3 Correct 16 ms 8148 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 17 ms 8092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8148 KB Output is correct
2 Correct 16 ms 8060 KB Output is correct
3 Correct 16 ms 8148 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 17 ms 8092 KB Output is correct
6 Correct 19 ms 8200 KB Output is correct
7 Correct 16 ms 8148 KB Output is correct
8 Correct 18 ms 8180 KB Output is correct
9 Correct 18 ms 8184 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8148 KB Output is correct
2 Correct 16 ms 8060 KB Output is correct
3 Correct 16 ms 8148 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 17 ms 8092 KB Output is correct
6 Correct 19 ms 8200 KB Output is correct
7 Correct 16 ms 8148 KB Output is correct
8 Correct 18 ms 8180 KB Output is correct
9 Correct 18 ms 8184 KB Output is correct
10 Correct 41 ms 8832 KB Output is correct
11 Correct 46 ms 8788 KB Output is correct
12 Correct 48 ms 8832 KB Output is correct
13 Correct 39 ms 8704 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8148 KB Output is correct
2 Correct 16 ms 8060 KB Output is correct
3 Correct 16 ms 8148 KB Output is correct
4 Correct 15 ms 8148 KB Output is correct
5 Correct 17 ms 8092 KB Output is correct
6 Correct 19 ms 8200 KB Output is correct
7 Correct 16 ms 8148 KB Output is correct
8 Correct 18 ms 8180 KB Output is correct
9 Correct 18 ms 8184 KB Output is correct
10 Correct 41 ms 8832 KB Output is correct
11 Correct 46 ms 8788 KB Output is correct
12 Correct 48 ms 8832 KB Output is correct
13 Correct 39 ms 8704 KB Output is correct
14 Correct 5489 ms 83300 KB Output is correct
15 Execution timed out 10013 ms 72564 KB Time limit exceeded
16 Halted 0 ms 0 KB -