Submission #251282

#	Time	Username	Problem	Language	Result	Execution time	Memory
251282		combi1k1	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	29 / 85	1593 ms	118008 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 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]);
}
 
unordered_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)   {
                int p = suffix_array[get_min(l,r)];

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

                int val = add(mul(H2,P[p - l]),H1);
                int pos = l;

                if (T)  pos = n - r + 1;

                Hash[t][r - l + 1][val] = pos;
            }
            reverse(s.begin(),s.end());
        }
    };
    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;
        }
    }
}

Compilation message (stderr)

necklace.cpp: In lambda function:
necklace.cpp:83:18: warning: variable 'get_rotation' set but not used [-Wunused-but-set-variable]
             auto get_rotation = [&](int l,int r)    {
                  ^~~~~~~~~~~~

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