oj.uz

답안 #582976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582976 2022-06-24T16:18:34 Z 600Mihnea Palindromic Partitions (CEOI17_palindromic) C++17
100 / 100
 5046 ms 83788 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 && pali(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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 14 ms 8148 KB Output is correct
4 Correct 15 ms 8156 KB Output is correct
5 Correct 14 ms 8068 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 14 ms 8148 KB Output is correct
4 Correct 15 ms 8156 KB Output is correct
5 Correct 14 ms 8068 KB Output is correct
6 Correct 15 ms 8140 KB Output is correct
7 Correct 14 ms 8156 KB Output is correct
8 Correct 15 ms 8148 KB Output is correct
9 Correct 15 ms 8084 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 14 ms 8148 KB Output is correct
4 Correct 15 ms 8156 KB Output is correct
5 Correct 14 ms 8068 KB Output is correct
6 Correct 15 ms 8140 KB Output is correct
7 Correct 14 ms 8156 KB Output is correct
8 Correct 15 ms 8148 KB Output is correct
9 Correct 15 ms 8084 KB Output is correct
10 Correct 39 ms 8900 KB Output is correct
11 Correct 29 ms 8836 KB Output is correct
12 Correct 43 ms 8828 KB Output is correct
13 Correct 33 ms 8724 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8148 KB Output is correct
2 Correct 15 ms 8148 KB Output is correct
3 Correct 14 ms 8148 KB Output is correct
4 Correct 15 ms 8156 KB Output is correct
5 Correct 14 ms 8068 KB Output is correct
6 Correct 15 ms 8140 KB Output is correct
7 Correct 14 ms 8156 KB Output is correct
8 Correct 15 ms 8148 KB Output is correct
9 Correct 15 ms 8084 KB Output is correct
10 Correct 39 ms 8900 KB Output is correct
11 Correct 29 ms 8836 KB Output is correct
12 Correct 43 ms 8828 KB Output is correct
13 Correct 33 ms 8724 KB Output is correct
14 Correct 4606 ms 74668 KB Output is correct
15 Correct 2537 ms 77608 KB Output is correct
16 Correct 5046 ms 83788 KB Output is correct
17 Correct 2355 ms 48184 KB Output is correct