oj.uz

Submission #99294

# Submission time Handle Problem Language Result Execution time Memory
99294 2019-03-02T08:33:13 Z mirbek01 Palindromes (APIO14_palindrome) C++11
47 / 100
 1000 ms 119340 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 2;
const int mod = 1e9 + 9;

int n, bor[26][N], cnt[N * 27], used[26], cn = 1;
long long ans, h[N], h1[N], pr = 101, pw[N];
string s;
unordered_map <int, int> mp;

int get(int l, int r){
      long long hs = (h[r] - h[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
int get1(int l, int r){
      long long hs = (h1[r] - h1[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
void add(int v, int id, int len, int c){
      while(1){
            if(id - len <= 0 || id + len + c > n || s[id - len] != s[id + len + c]){
                  break;
            }
            int now = s[id - len] - 'a';
            if(!bor[now][v]){
                  bor[now][v] = ++ cn;
            }
            v = bor[now][v];
            mp[get(id - len, id)] = v;
            len ++;
      }
      cnt[v] ++;
}
void f(int v, int len, int c){
      for(int i = 0; i < 26; i ++){
            if(bor[i][v]){
                  f(bor[i][v], len + 1, c);
                  cnt[v] += cnt[bor[i][v]];
            }
      }
      ans = max(ans, (len * 2 - c) * 1ll * cnt[v]);
}

int main(){
      cin >> s;
      n = s.size();
      s = ' ' + s;
      pw[0] = pr;
      for(int i = 1; i < N; i ++)
            pw[i] = (pw[i - 1] * pr) % mod;
      for(int i = 1; i <= n; i ++){
            h[i] = (h[i - 1] + (s[i] - 'a' + 1) * pw[i]) % mod;
            h1[i] = (h1[i - 1] + (s[n - i + 1] - 'a' + 1) * pw[i]) % mod;
      }
      for(int i = 1; i <= n; i ++){
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 0);
                  continue;
            }
            int lo = max(1, i - (n - i)), hi = i, pos;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  int f = get(md, i + (i - md)), s = get1(n - (i + (i - md)) + 1, n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 0);
      }
      f(1, 0, 1);
      memset(bor, 0, sizeof(bor));
      memset(cnt, 0, sizeof(cnt));
      memset(used, 0, sizeof(used));
      cn = 1;
      mp.clear();
      for(int i = 1; i < n; i ++){
            if(s[i] != s[i + 1])
                  continue;
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 1);
                  continue;
            }
            int lo = max(1, i - (n - i - 1)), hi = i, pos = -1;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  int f = get(md, i + (i - md) + 1), s = get1(n - (i + (i - md) + 1) + 1, n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 1);
      }
      f(1, 0, 0);
      cout << ans << endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
       hs = (hs * pw[N - l]) % mod;
                     ~~^~~
palindrome.cpp:65:51: note: 'pos' was declared here
             int lo = max(1, i - (n - i)), hi = i, pos;
                                                   ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 64860 KB Output is correct
2 Correct 66 ms 64936 KB Output is correct
3 Correct 59 ms 64888 KB Output is correct
4 Correct 60 ms 64860 KB Output is correct
5 Correct 53 ms 64888 KB Output is correct
6 Correct 63 ms 64880 KB Output is correct
7 Correct 58 ms 64860 KB Output is correct
8 Correct 63 ms 64920 KB Output is correct
9 Correct 56 ms 64860 KB Output is correct
10 Correct 64 ms 65004 KB Output is correct
11 Correct 59 ms 64936 KB Output is correct
12 Correct 58 ms 64880 KB Output is correct
13 Correct 58 ms 64888 KB Output is correct
14 Correct 57 ms 64888 KB Output is correct
15 Correct 65 ms 65020 KB Output is correct
16 Correct 62 ms 64888 KB Output is correct
17 Correct 56 ms 64888 KB Output is correct
18 Correct 71 ms 64888 KB Output is correct
19 Correct 60 ms 64888 KB Output is correct
20 Correct 60 ms 64888 KB Output is correct
21 Correct 62 ms 65020 KB Output is correct
22 Correct 56 ms 64888 KB Output is correct
23 Correct 57 ms 64888 KB Output is correct
24 Correct 56 ms 64888 KB Output is correct
25 Correct 55 ms 64892 KB Output is correct
26 Correct 57 ms 64888 KB Output is correct
27 Correct 59 ms 64888 KB Output is correct
28 Correct 54 ms 64888 KB Output is correct
29 Correct 63 ms 65016 KB Output is correct
30 Correct 54 ms 64888 KB Output is correct
31 Correct 68 ms 64888 KB Output is correct
32 Correct 55 ms 64888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64992 KB Output is correct
2 Correct 64 ms 65016 KB Output is correct
3 Correct 57 ms 65016 KB Output is correct
4 Correct 56 ms 65144 KB Output is correct
5 Correct 57 ms 64988 KB Output is correct
6 Correct 56 ms 65020 KB Output is correct
7 Correct 55 ms 65144 KB Output is correct
8 Correct 56 ms 65016 KB Output is correct
9 Correct 56 ms 65148 KB Output is correct
10 Correct 62 ms 65272 KB Output is correct
11 Correct 58 ms 65272 KB Output is correct
12 Correct 56 ms 65144 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 65776 KB Output is correct
2 Correct 75 ms 66672 KB Output is correct
3 Correct 70 ms 65656 KB Output is correct
4 Correct 86 ms 66424 KB Output is correct
5 Correct 93 ms 68080 KB Output is correct
6 Correct 88 ms 67972 KB Output is correct
7 Correct 88 ms 66676 KB Output is correct
8 Correct 106 ms 68832 KB Output is correct
9 Correct 100 ms 68872 KB Output is correct
10 Correct 89 ms 67064 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 73792 KB Output is correct
2 Correct 406 ms 79336 KB Output is correct
3 Correct 353 ms 71876 KB Output is correct
4 Correct 469 ms 75828 KB Output is correct
5 Correct 938 ms 99452 KB Output is correct
6 Correct 778 ms 95208 KB Output is correct
7 Correct 815 ms 93084 KB Output is correct
8 Execution timed out 1082 ms 119340 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 60448 KB Time limit exceeded
2 Halted 0 ms 0 KB -