Submission #716803

#	Time	Username	Problem	Language	Result	Execution time	Memory
716803		vjudge1	Palindromes (APIO14_palindrome)	C++17	23 / 100	1053 ms	131072 KiB

palindrome

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
struct segment{int l, r, id;
int size(){return r-l+1;}};
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e5 + 100;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n;
string s;
vector<ll> g[maxn];
ll pref[maxn];
ll suf[maxn];
ll pw[maxn];

int ok(int l, int r){
    ll num1 = pref[r] - pref[l-1] * pw[r - l + 1] % MOD;
    ll num2 = suf[l] - suf[r+1] * pw[r - l + 1] % MOD;
    if(num1 < 0) num1 += MOD;
    if(num2 < 0) num2 += MOD;
    return num1 == num2;
}

void test(){
    cin >> s;
    n = s.size();
    s = '#' + s;
    pw[0] = 1;
    for(int i = 1; i <= n; i++){
        pref[i] = (pref[i-1] * P + s[i] - 'a' + 1) % MOD;
        pw[i] = (pw[i-1] * P) % MOD;
    }
    for(int i = n; i > 0; i--){
        suf[i] = (suf[i + 1] * P + s[i] - 'a' + 1) % MOD;
    }
    for(int l = 1; l <= n; l++){
        for(int r = l; r <= n; r++){
            if(ok(l, r)){
                g[r - l + 1].push_back((pref[r] - pref[l-1] * pw[r - l + 1] % MOD + MOD) % MOD);
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        sort(g[i].begin(), g[i].end());
        int cnt = 0;
        for(int j = 0; j < g[i].size(); j++){
            if(j == 0 || g[i][j] != g[i][j-1]) cnt = 0;
            cnt++; ans = max(ans, 1ll * cnt * i);
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

Compilation message (stderr)

palindrome.cpp: In function 'void test()':
palindrome.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < g[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

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