oj.uz

Submission #47336

# Submission time Handle Problem Language Result Execution time Memory
47336 2018-05-01T05:53:32 Z Talant Palindromes (APIO14_palindrome) C++17
0 / 100
 1000 ms 5700 KB 
#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e18 + 7;
const int N = (int)2e6 + 7;

int p = 997;
int hs[N],inv[N],pw[N];
int n,ans;

string a;
int u[N];

void f (int l,int r) {
      int lst= 0;
      if (l > 0)
            lst = hs[l - 1];

      int o = hs[r] - lst;

      o *= pw[n - l];

      o += inf;
      o %= N;
      u[o] ++;
      ans = max(ans,u[o] * (r - l + 1));
}
bool check(int l,int r) {
      int s1 = 0,s2 = 0;
      if (l > 0)
            s1 = hs[l - 1];
      if (r < n - 1)
            s2 = inv[r + 1];

      int o1 = hs[r] - s1;
      int o2 = inv[l] - s2;

      if (l > n - r - 1)
            o2 *= pw[l - (n - r - 1)];
      else
            o1 *= pw[n - r - 1 - l];

      return (o2 == o1);
}
main () {
      pw[0] = 1;
      for (int i = 1; i <= 10010; i ++) {
            pw[i] = pw[i - 1] * p;
            pw[i] %= N;
      }

      cin >> a;

      n = a.size();

      hs[0] = (int)(a[0] - 'a' + 1);

      for (int i = 1; i < n; i ++)
            hs[i] = hs[i - 1] + (pw[i] * (int)(a[i] - 'a' + 1));

      inv[n] = 0;
      for (int i = n - 1; i >= 0; i --)
            inv[i] = inv[i + 1] + (pw[n - i - 1] * (int)(a[i] - 'a' + 1));

      for (int i = 0; i < n; i ++) {
            for (int j = i; j < n; j ++) {
                  if (check(i,j)) {
                        f(i,j);
                  }
            }
      }
      cout << ans << endl;
}

Compilation message

palindrome.cpp:54:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 520 KB Output is correct
3 Incorrect 2 ms 572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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