제출 #670818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670818		fatemetmhr	회문 (APIO14_palindrome)	C++17	100 / 100	965 ms	107252 KiB

palindrome

// ~ Be Name Khoda ~ 
 
#include <bits/stdc++.h>

#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
typedef long long ll;
 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
 
const int maxn5 = 3e5 + 10;
const int lg    = 19;
const ll  inf   = 1e18;
const int al    = 200;
 
int rnk[lg][maxn5], a[maxn5], lef[maxn5], rig[maxn5];
int val[maxn5], mn[maxn5], lcp[maxn5], rev[maxn5];
int cmpid, lenlen, cmpsz, z[2][maxn5];
set <int> av[2];
vector <int> srt[maxn5];
vector <pair<int, int>> ed;
vector <pair<int, pair<int, int>>> have;
vector <pair<pair<int, int>, int>> req;
 
inline int get_lcp(int v, int u){
    int ans = 0;
    for(int i = lg - 1; i >= 0; i--) if(rnk[i][u] == rnk[i][v]){
        u += (1 << i);
        v += (1 << i);
        ans += (1 << i);
    }
    return ans;
}
 
inline void fix2(int& a){
    if(a < 0)
        a += cmpsz;
    if(a >= cmpsz)
        a -= cmpsz;
}

inline int fix(int a){
    if(a >= cmpsz)
        a -= cmpsz;
    return a;
}
 
inline bool cmp(int i, int j){
    return rnk[cmpid][i] < rnk[cmpid][j] || (rnk[cmpid][i] == rnk[cmpid][j] && rnk[cmpid][fix(i + lenlen)] < rnk[cmpid][fix(j + lenlen)]);
}
 
inline void sort1(int n){
    for(int i = 0; i < max(n, al); i++)
        srt[i].clear();
    for(int i = 0; i < n; i++)
        srt[rnk[cmpid][fix(i + lenlen)]].pb(i);
    int pt = 0;
    for(int i = 0; i < max(n, al); i++)
        for(auto u : srt[i])
            a[pt++] = u;
}
 
inline void sort(){
    int n = cmpsz;
    for(int i = 0; i < n; i++)
        srt[rnk[cmpid][a[i]]].pb(a[i]);
    int pt = 0;
    for(int i = 0; i < max(n, al); i++){
        for(auto u : srt[i])
            a[pt++] = u;
        srt[i].clear();
    }
}
 
inline void build_sf(string s){
    s.pb('#');
    int n = cmpsz = s.size();
    for(int i = 0; i < n; i++){
        rnk[0][i] = int(s[i]);
        srt[rnk[0][i]].pb(i);
    }
    int pt = 0;
    for(int i = 0; i < al; i++) for(auto u : srt[i])
        a[pt++] = u;
    for(int i = 0; i < al; i++)
        srt[i].clear();
    for(int j = 1; j < lg; j++){
        cmpid = j - 1; lenlen = (1 << cmpid) % n;
        for(int i = 0; i < n; i++)
            fix2(a[i] = a[i] - lenlen);
        sort();
        rnk[j][a[0]] = 0;
        for(int i = 1; i < n; i++){
            rnk[j][a[i]] = rnk[j][a[i - 1]] + cmp(a[i - 1], a[i]);
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    string s; cin >> s;
    int n = s.size();
 
    build_sf(s);
    for(int i = 0; i < n; i++)
        a[i] = a[i + 1];
 
    for(int i = 1; i < n; i++){
        lcp[i] = get_lcp(a[i - 1], a[i]);
        ed.pb({lcp[i], i});
    }
    ll ans = 0;
    //cout << t << endl;
    for(int i = 0; i < n; i++){
        //cout << a[i] << ' ';
        rev[a[i]] = i;
        lef[i] = rig[i] = i;
    }
 
    int l = 0, r = 0;
    for(int i = 0; i < n; i++){
        if(i){
            if(r >= i)
                z[1][i] = min(r - i + 1, z[1][r + l - i + 1]);
            while(z[1][i] + i < n && i - z[1][i] - 1 >= 0 && s[i + z[1][i]] == s[i - z[1][i] - 1])
                z[1][i]++;
            have.pb({i - z[1][i], {1, i - 1}});
            ans = max(ans, z[1][i] * 2LL);
            if(i + z[1][i] - 1 > r){
                r = i + z[1][i] - 1;
                l = i - z[1][i];
            }
        }
        if(r >= i)
            z[0][i] = min(r - i + 1, z[0][r + l - i]);
        while(z[0][i] + i < n && i - z[0][i] >= 0 && s[i + z[0][i]] == s[i - z[0][i]])
            z[0][i]++;
        have.pb({i - z[0][i] + 1, {0, i}});
        if(i + z[0][i] - 1 > r){
            r = i + z[0][i] - 1;
            l = i - z[0][i] + 1;
        }
        ans = max(ans, z[0][i] * 2LL - 1);
    }
 
    sort(all(ed));
    while(ed.size()){
        int id = ed.back().se, len = ed.back().fi;
        ed.pop_back();
        int l, r;
        lef[rig[id]] = l = lef[id - 1];
        rig[lef[id - 1]] = r = rig[id];
        req.pb({{a[l], len}, r - l + 1});
    }
 
    sort(all(req));
    sort(all(have));
    int ind = 0;
    //cout << "having " << ans << endl;
 
    for(auto [b, val] : req){
        int l = b.fi, len = b.se;
        //cout << "A request of " << l << ' ' << len << ' ' << val << endl;
        while(ind < have.size() && have[ind].fi <= l){
            av[have[ind].se.fi].insert(have[ind].se.se);
            //cout << "adding " << have[ind].fi << ' ' << have[ind].se.fi << ' ' << have[ind].se.se << endl;
            ind++;
        }
        int klen = len / 2;
        int slen = klen + len % 2;
        auto it = av[0].upper_bound(l + slen - 1);
        if(av[0].size() && it != av[0].begin()){
            it--;
            ans = max(ans, ll(val) * (((*it) - l) * 2 + 1));
            //cout << "well fard " << (*it) << ' ' << ans << endl;
        }
        it = av[1].upper_bound(l + klen - 1);
        if(av[1].size() && it != av[1].begin()){
            it--;
            ans = max(ans, ll(val) * ((*it) - l + 1) * 2);
            //cout << "well zoj " << (*it) << ' ' << ans << endl;
        }
    }
 
    cout << ans << endl;
 
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:173:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         while(ind < have.size() && have[ind].fi <= l){
      |               ~~~~^~~~~~~~~~~~~

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