oj.uz

Submission #164553

# Submission time Handle Problem Language Result Execution time Memory
164553 2019-11-21T12:24:49 Z combi1k1 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
9 / 85
 1500 ms 109200 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]);
}

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

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 1656 KB Output is partially correct
2 Correct 5 ms 1656 KB Output is correct
3 Correct 5 ms 1532 KB Output is correct
4 Correct 5 ms 1656 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 6 ms 1656 KB Output is partially correct
2 Correct 5 ms 1656 KB Output is correct
3 Correct 5 ms 1532 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 42 ms 6136 KB Output is correct
7 Correct 52 ms 7288 KB Output is correct
8 Partially correct 32 ms 5496 KB Output is partially correct
9 Partially correct 62 ms 8568 KB Output is partially correct
10 Correct 82 ms 11356 KB Output is correct
11 Correct 95 ms 11320 KB Output is correct
12 Correct 53 ms 7672 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 1656 KB Output is partially correct
2 Correct 5 ms 1656 KB Output is correct
3 Correct 5 ms 1532 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 42 ms 6136 KB Output is correct
7 Correct 52 ms 7288 KB Output is correct
8 Partially correct 32 ms 5496 KB Output is partially correct
9 Partially correct 62 ms 8568 KB Output is partially correct
10 Correct 82 ms 11356 KB Output is correct
11 Correct 95 ms 11320 KB Output is correct
12 Correct 53 ms 7672 KB Output is correct
13 Execution timed out 1551 ms 109200 KB Time limit exceeded
14 Halted 0 ms 0 KB -