oj.uz

Submission #164545

# Submission time Handle Problem Language Result Execution time Memory
164545 2019-11-21T11:57:53 Z combi1k1 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1500 ms 116460 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 2040 KB Output is partially correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 6 ms 1784 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 2040 KB Output is partially correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 6 ms 1784 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 94 ms 12024 KB Output is correct
7 Correct 96 ms 12228 KB Output is correct
8 Partially correct 78 ms 10748 KB Output is partially correct
9 Partially correct 92 ms 11768 KB Output is partially correct
10 Correct 99 ms 11896 KB Output is correct
11 Correct 108 ms 12048 KB Output is correct
12 Correct 86 ms 11228 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 2040 KB Output is partially correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 6 ms 1784 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 94 ms 12024 KB Output is correct
7 Correct 96 ms 12228 KB Output is correct
8 Partially correct 78 ms 10748 KB Output is partially correct
9 Partially correct 92 ms 11768 KB Output is partially correct
10 Correct 99 ms 11896 KB Output is correct
11 Correct 108 ms 12048 KB Output is correct
12 Correct 86 ms 11228 KB Output is correct
13 Execution timed out 1569 ms 116460 KB Time limit exceeded
14 Halted 0 ms 0 KB -