oj.uz

Submission #71854

# Submission time Handle Problem Language Result Execution time Memory
71854 2018-08-25T17:20:00 Z evpipis Palindromes (APIO14_palindrome) C++11
73 / 100
 1000 ms 61412 KB 
#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;
}

bool comp(int a, int b){
    int c = lcp(a, b);
    return (str[a+c] < str[b+c]);
}

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];
    }

    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;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 10 ms 7564 KB Output is correct
3 Correct 10 ms 7564 KB Output is correct
4 Correct 9 ms 7564 KB Output is correct
5 Correct 9 ms 7564 KB Output is correct
6 Correct 10 ms 7564 KB Output is correct
7 Correct 9 ms 7564 KB Output is correct
8 Correct 9 ms 7564 KB Output is correct
9 Correct 8 ms 7564 KB Output is correct
10 Correct 9 ms 7584 KB Output is correct
11 Correct 8 ms 7712 KB Output is correct
12 Correct 9 ms 7712 KB Output is correct
13 Correct 9 ms 7720 KB Output is correct
14 Correct 10 ms 7720 KB Output is correct
15 Correct 10 ms 7720 KB Output is correct
16 Correct 8 ms 7720 KB Output is correct
17 Correct 11 ms 7720 KB Output is correct
18 Correct 10 ms 7720 KB Output is correct
19 Correct 9 ms 7720 KB Output is correct
20 Correct 9 ms 7720 KB Output is correct
21 Correct 8 ms 7720 KB Output is correct
22 Correct 8 ms 7720 KB Output is correct
23 Correct 9 ms 7720 KB Output is correct
24 Correct 8 ms 7720 KB Output is correct
25 Correct 8 ms 7720 KB Output is correct
26 Correct 7 ms 7720 KB Output is correct
27 Correct 7 ms 7720 KB Output is correct
28 Correct 8 ms 7720 KB Output is correct
29 Correct 9 ms 7720 KB Output is correct
30 Correct 9 ms 7720 KB Output is correct
31 Correct 8 ms 7720 KB Output is correct
32 Correct 9 ms 7720 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7804 KB Output is correct
2 Correct 9 ms 7804 KB Output is correct
3 Correct 9 ms 7824 KB Output is correct
4 Correct 9 ms 7840 KB Output is correct
5 Correct 9 ms 7840 KB Output is correct
6 Correct 9 ms 7840 KB Output is correct
7 Correct 10 ms 7840 KB Output is correct
8 Correct 9 ms 7840 KB Output is correct
9 Correct 9 ms 7840 KB Output is correct
10 Correct 8 ms 7840 KB Output is correct
11 Correct 9 ms 7840 KB Output is correct
12 Correct 12 ms 7840 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9468 KB Output is correct
2 Correct 22 ms 9472 KB Output is correct
3 Correct 23 ms 9596 KB Output is correct
4 Correct 31 ms 9600 KB Output is correct
5 Correct 26 ms 9600 KB Output is correct
6 Correct 23 ms 9600 KB Output is correct
7 Correct 25 ms 9600 KB Output is correct
8 Correct 30 ms 9600 KB Output is correct
9 Correct 25 ms 9600 KB Output is correct
10 Correct 21 ms 9600 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 25076 KB Output is correct
2 Correct 194 ms 25076 KB Output is correct
3 Correct 209 ms 25580 KB Output is correct
4 Correct 193 ms 25580 KB Output is correct
5 Correct 203 ms 25580 KB Output is correct
6 Correct 215 ms 25580 KB Output is correct
7 Correct 245 ms 25580 KB Output is correct
8 Correct 266 ms 25580 KB Output is correct
9 Correct 305 ms 25580 KB Output is correct
10 Correct 237 ms 25580 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 59364 KB Output is correct
2 Correct 747 ms 59364 KB Output is correct
3 Correct 736 ms 61412 KB Output is correct
4 Correct 686 ms 61412 KB Output is correct
5 Correct 834 ms 61412 KB Output is correct
6 Correct 759 ms 61412 KB Output is correct
7 Correct 724 ms 61412 KB Output is correct
8 Execution timed out 1082 ms 61412 KB Time limit exceeded
9 Halted 0 ms 0 KB -