제출 #164545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164545		combi1k1	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	9 / 85	1569 ms	116460 KiB

necklace

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

set<ii> 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].insert(ii(mul(f[0][l][r],f[1][n - r + 1][n - l + 1]),l));
    };

    build(0);
    build(1);

    int len = 0;
    int st1 = 1;
    int st2 = 1;

    for(int L = 1 ; L < N ; ++L)
    for(ii  x : Hash[0][L]) {
        int H = x.X;
        auto it = Hash[1][L].lower_bound(ii(H,0));
        if (it != Hash[1][L].end() && (*it).X == H)
            len = L,
            st1 = x.Y,
            st2 = (*it).Y;
    }

    cout << len << "\n";
    cout << st1 - 1 << " ";
    cout << st2 - 1 << endl;
}

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 0 / 40