제출 #670293

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

palindrome

// hmmm... na dige chizi baraye goftan namoonde


#include <bits/stdc++.h>

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 = 6e5 + 10;
const int lg    = 21;
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;
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 void build_rmq(int n){
    for(int i = 0; i < n; i++)
        rnk[0][i] = lcp[i];
    for(int j = 1; j < lg; j++) for(int i = 0; (i + (1 << j) - 1) < n; i++)
        rnk[j][i] = min(rnk[j - 1][i], rnk[j - 1][i + (1 << (j - 1))]);
}


inline int get_min(int l, int r){
    if(r < l)
        swap(l, r);
    l++;
    int k = 31 - __builtin_clz(r - l + 1);
    return min(rnk[k][l], rnk[k][r - (1 << k) + 1]);
}

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 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 sort2(int n){
    for(int i = 0; i < max(n, al); i++)
        srt[i].clear();
    for(int i = 0; i < n; i++){
        srt[rnk[cmpid][a[i]]].pb(a[i]);
        //cout << "look! " << i << ' ' << a[i] << endl;
    }
    int pt = 0;
    for(int i = 0; i < max(n, al); i++)
        for(auto u : srt[i])
            a[pt++] = u;
}

inline void build_sf(string s){
    int n = cmpsz = s.size();
    for(int i = 0; i < n; i++)
        rnk[0][i] = int(s[i]);
    for(int j = 1; j < lg; j++){
        for(int i = 0; i < n; i++)
            a[i] = i;
        cmpid = j - 1; lenlen = (1 << cmpid) % n;
        //cout << "having " << j << ' ' << lenlen << endl;
        sort1(n);
        sort2(n);
        rnk[j][a[0]] = 0;
        //cout << "& " << j << ' ' << 0 << ' ' << a[0] << ' ' << 0 << endl;
        for(int i = 1; i < n; i++){
            rnk[j][a[i]] = rnk[j][a[i - 1]] + cmp(a[i - 1], a[i]);
            //cout << "& " << j << ' ' << i << ' ' << a[i] << ' ' << rnk[j][a[i]] << endl;
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    string s; cin >> s;
    int n = s.size();

    string t = s + "$";
    reverse(all(s));
    t = t + s + "#";
    reverse(all(s));
    build_sf(t);
    int m = t.size();

    for(int i = 1; i < m; i++){
        lcp[i] = get_lcp(a[i - 1], a[i]);
        //cout << "aha " << i << ' ' << a[i - 1] << ' ' << a[i] << ' ' << lcp[i] << endl;
        ed.pb({lcp[i], i});
    }
    ll ans = 0;
    //cout << t << endl;
    for(int i = 0; i < m; i++){
        //cout << a[i] << ' ';
        rev[a[i]] = i;
        lef[i] = rig[i] = i;
        val[i] = (a[i] < n);
        mn[i] = a[i];
    }
    //cout << endl;
    build_rmq(m);
    for(int i = 0; i < n; i++){
        ll plf = get_min(rev[i], rev[2 * n - i]); // lzoomn l < r nist!!!!!!!!!!!!
        have.pb({i - plf + 1, {0, i}});
        ans = max(ans, plf * 2 - 1);
        //cout << i << ' ' << plf << ' ' << rev[i] << ' ' << rev[2 * n - i] << ' ' << 2 * n - i << endl;
        if(i){
            ll plz = get_min(rev[i], rev[2 * n - i + 1]);
            //cout << "aha plz of " << i << ' ' << plz << endl;
            if(plz){
                ans = max(ans, plz * 2);
                have.pb({i - plz, {1, i - 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];
        val[l] = val[r] = val[l] + val[r];
        mn[l] = mn[r] = min(mn[l], mn[r]);
        if(val[l])
            req.pb({{mn[l], len}, val[l]});
    }

    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;

}

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

palindrome.cpp: In function 'int main()':
palindrome.cpp:175: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]
  175 |         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: 0 / 27