Submission #47336

#	Time	Username	Problem	Language	Result	Execution time	Memory
47336		Talant	Palindromes (APIO14_palindrome)	C++17	0 / 100	1078 ms	5700 KiB

palindrome

#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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27