제출 #71865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71865		evpipis	회문 (APIO14_palindrome)	C++14	100 / 100	973 ms	61544 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 3e5+5, mod = 1e9+7, base = 57;
int suf[len], has1[len], has2[len], po[len], lim[len], n, lef[len], rig[len];
int tmp[len], ran[len], cnt[len];
char str[len];
vector<int> vec[len];
vector<ii> st;
set<int> mys;

inline int add(int a, int b){
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

inline int sub(int a, int b){
    a -= b;
    if (a < 0) a += mod;
    return a;
}

int mul(int a, int b){
    return (a*1LL*b)%mod;
}

inline int val1(int l, int r){
    l++, r++;
    return sub(has1[r], mul(has1[l-1], po[r-l+1]));
}

inline int val2(int l, int r){
    return (sub(has2[l], mul(has2[r+1], po[r-l+1])));
}

int lcp(int a, int b){
    int l = 1, r = n-1-max(a, b)+1, ans = 0;
    while (l <= r){
        int mid = (l+r)/2;
        if (val1(a, a+mid-1) == val1(b, b+mid-1))
            ans = mid, l = mid+1;
        else
            r = mid-1;
    }

    return ans;
}

int bs(int i, int t){
    int l = 1, r = min(n-i-t, i+1), ans = 0;
    while (l <= r){
        int mid = (l+r)/2;
        if (val1(i-mid+1, i+t+mid-1) == val2(i-mid+1, i+t+mid-1))
            ans = 2*mid - (1-t), l = mid+1;
        else
            r = mid-1;
    }

    return ans;
}

void radix(int k){
    for (int i = 0; i <= max(n, 300); i++)
        cnt[i] = 0;
    for (int i = 0; i < n; i++)
        cnt[(suf[i]+k<n?ran[suf[i]+k]:0)+1]++;
    for (int i = 1; i <= max(n, 300); i++)
        cnt[i] += cnt[i-1];

    for (int i = 0; i < n; i++)
        tmp[cnt[(suf[i]+k<n?ran[suf[i]+k]:0)]++] = suf[i];
    for (int i = 0; i < n; i++)
        suf[i] = tmp[i];
}

int main(){
    scanf("%s", &str);
    n = strlen(str);
    str[n++] = 0;

    po[0] = 1;
    for (int i = 1; i <= n; i++)
        po[i] = mul(po[i-1], base);
    for (int i = 1; i <= n; i++)
        has1[i] = add(mul(has1[i-1], base), str[i-1]-'a');
    for (int i = n-1; i >= 0; i--)
        has2[i] = add(mul(has2[i+1], base), str[i]-'a');

    for (int i = 0; i < n; i++)
        suf[i] = i;
    //sort(suf, suf+n, comp); // suffix array before :(

    for (int i = 0; i < n; i++)
        ran[i] = str[i];
    for (int k = 1; k <= n; k*=2){
        radix(k);
        radix(0);

        int ptr = -1;
        for (int i = 0; i < n; i++){
            if (i == 0 || ran[suf[i]] != ran[suf[i-1]] || ran[suf[i]+k] != ran[suf[i-1]+k])
                tmp[suf[i]] = ++ptr;
            else
                tmp[suf[i]] = ptr;
        }

        for (int i = 0; i < n; i++)
            ran[i] = tmp[i];

        if (ptr == n-1) break;
    }

    for (int i = 0; i < n; i++)
        lim[i] = -1;
    for (int i = 0; i < n-1; i++)
        lim[suf[i]] = lcp(suf[i], suf[i+1]);

    //for (int i = 0; i < n; i++)
      //  printf("%d ", suf[i]);
    //printf("\n");

    ll ans = 0;
    for (int i = 0; i < n; i++){
        int temp = bs(i, 0);
        vec[i-temp/2].pb(temp);
        ans = max(ans, (ll)temp);

        //printf("i = %d, mx0 = %d\n", i, temp);

        temp = bs(i, 1);
        vec[i-temp/2+1].pb(temp);
        ans = max(ans, (ll)temp);

        //printf("i = %d, mx1 = %d\n", i, temp);
    }

    int k = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < vec[i].size(); j++)
            mys.insert(vec[i][j]-k);

        set<int>::iterator it = mys.upper_bound(lim[i]-k);
        if (lim[i] != -1 && it != mys.begin()){
            it = prev(it);
            lim[i] = *it + k;
        }
        else
            lim[i] = 0;

        k-=2;
    }

    //for (int i = 0; i < n-1; i++)
      //  printf("%d ", lim[suf[i]]);
    //printf("\n");

    st.pb(mp(-1, -1));
    for (int i = 0; i < n-1; i++){
        while (lim[suf[i]] <= st.back().fi)
            st.pop_back();
        lef[i] = st.back().se;
        st.pb(mp(lim[suf[i]], i));
    }

    st.clear(), st.pb(mp(-1, n-1));
    for (int i = n-2; i >= 0; i--){
        while (lim[suf[i]] <= st.back().fi)
            st.pop_back();
        rig[i] = st.back().se;
        st.pb(mp(lim[suf[i]], i));
    }

    for (int i = 0; i < n-1; i++)
        ans = max(ans, lim[suf[i]] * 1LL * (rig[i]-lef[i]));
    printf("%lld\n", ans);
    return 0;
}

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

palindrome.cpp: In function 'int main()':
palindrome.cpp:85:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
     scanf("%s", &str);
                 ~~~~^
palindrome.cpp:147:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~
palindrome.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", &str);
     ~~~~~^~~~~~~~~~~~

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