Submission #164553

#TimeUsernameProblemLanguageResultExecution timeMemory
164553combi1k1Necklace (Subtask 1-3) (BOI19_necklace1)C++14
9 / 85
1551 ms109200 KiB
#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

const int   N   = 3e3 + 1;
const int   mod = 1e9 + 7;

typedef pair<int,int>   ii;

int add(int a,int b)    {
    a += b;
    if (a >= mod)
        a -= mod;
    return  a;
}
int sub(int a,int b)    {
    a -= b;
    if (a < 0)
        a += mod;
    return  a;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}

int H[N];
int P[N];
int f[2][N][N];

int get(int i,int L)    {
    return  sub(H[i + L - 1],mul(H[i - 1],P[L]));
}

int rmq[N][20];

int get_min(int l,int r)    {
    int k = log2(r - l + 1);
    return  min(rmq[l][k],rmq[r - (1 << k) + 1][k]);
}

map<int,int> Hash[2][N];

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

    auto build = [&](int t) {
        string s;
        cin >> s;

        int n = s.size();

        for(int T = 0 ; T < 2 ; ++T)    {
            P[0] = 1;

            for(int i = 1 ; i <= n ; ++i)   {
                P[i] = mul(P[i - 1],29);
                H[i] = mul(H[i - 1],29);
                H[i] = add(H[i],s[i - 1] - 'a' + 1);
            }
            H[n + 1] = mul(H[n],29);

            auto cmp = [&](int i,int j) {
                int l = 1;
                int r = n - max(i,j) + 2;
                while (l < r)   {
                    int m = (l + r) / 2;
                    if (get(i,m) != get(j,m))
                        r = m;
                    else
                        l = m + 1;
                }
                i += l - 1;
                j += l - 1;
                return  get(i,1) < get(j,1);
            };

            vector<int> suffix_array;

            suffix_array.resize(n);

            iota(suffix_array.begin(),suffix_array.end(),1);
            sort(suffix_array.begin(),suffix_array.end(),cmp);

            for(int i = 0 ; i < n ; ++i)
                rmq[suffix_array[i]][0] = i;

            for(int i = 0 ; (2 << i) <= n ; ++i)
            for(int j = 1 ; (2 << i) + j - 1 <= n ; ++j)
                rmq[j][i + 1] = min(rmq[j][i],rmq[j + (1 << i)][i]);

            auto get_rotation = [&](int l,int r)    {
                int p = suffix_array[get_min(l,r)];

                int H1 = get(l,p - l);
                int H2 = get(p,r - p + 1);

                return  add(mul(H2,P[p - l]),H1);
            };
            for(int l = 1 ; l <= n ; ++l)
            for(int r = l ; r <= n ; ++r)
                f[T][l][r] = get_rotation(l,r);

            reverse(s.begin(),s.end());
        }

        for(int l = 1 ; l <= n ; ++l)
        for(int r = l ; r <= n ; ++r)
            Hash[t][r - l + 1][mul(f[0][l][r],f[1][n - r + 1][n - l + 1])] = l;
    };

    build(0);
    build(1);

    for(int L = N - 1 ; L ; --L)
    for(auto it : Hash[0][L])   {
        int H = it.X;
        if (Hash[1][L].count(H))    {
            cout << L << "\n";
            cout << Hash[0][L][H] - 1 << " ";
            cout << Hash[1][L][H] - 1 << endl;
            return  0;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...