fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  3. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  4. #define pub push_back
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define int long long
  9. using namespace std;
  10.  
  11. const int N = 4000 + 5;
  12. const int M = 350;
  13. const int mod1 = 1e9 + 7;
  14. const int mod2 = 2e9 + 11;
  15. const int LOG = 19;
  16. const long long inf = 3e18;
  17.  
  18. string s, t;
  19. int n;
  20. bool is[N][N];
  21. int f[N][N], prefix[N];
  22.  
  23. void input() {
  24.     cin >> s;
  25.     n = s.size();
  26.     s = ' ' + s;
  27. }
  28. void solve() {
  29.     input();
  30.     FOR(i, 1, n, 1) {
  31.         is[i][i] = 1;
  32.         f[i][i] = 1;
  33.     }
  34.     FOR(i, 1, n - 1, 1) {
  35.         if (s[i] == s[i + 1]) {
  36.             is[i][i + 1] = 1;
  37.             f[i][i + 1] = 2;
  38.         }
  39.     }
  40.     FOD(i, n, 1, 1) {
  41.         FOR(j, i + 1, n, 1) {
  42.             if (is[i][j]) continue;
  43.             if (s[i] == s[j]) {
  44.                 is[i][j] = (is[i][j] || is[i + 1][j - 1]);
  45.                 if (is[i][j]) {
  46.                     int mid = (i + j) >> 1;
  47.                     int len = j - i + 1;
  48.                     if (len % 2 == 1) {
  49.                         f[i][j] = f[i][mid - 1] + 1;
  50.                     }
  51.                     if (len % 2 == 0) {
  52.                         f[i][j] = f[i][mid] + 1;
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     FOR(i, 1, n, 1) FOR(j, i, n, 1) {
  59.         if (is[i][j]) {
  60.             int x = f[i][j];
  61.             if (x == 0) continue;
  62.             prefix[1] ++;
  63.             prefix[x + 1] --;
  64.         }
  65.     }
  66.     FOR(i, 1, n, 1) {
  67.         prefix[i] = prefix[i - 1] + prefix[i];
  68.         cout << prefix[i] << " ";
  69.     }
  70. }
  71. signed main() {
  72.     #define name "baitap"
  73.     if (ifstream(name".inp")) {
  74.         freopen(name".inp", "r", stdin);
  75.         freopen(name".out", "w", stdout);
  76.     }
  77.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  78.     solve();
  79. }
  80.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c9dRQm
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!