oj.uz

Submission #251282

# Submission time Handle Problem Language Result Execution time Memory
251282 2020-07-20T16:40:48 Z combi1k1 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
29 / 85
 1500 ms 118008 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 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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 5 ms 1408 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 5 ms 1408 KB Output is correct
6 Correct 41 ms 3576 KB Output is correct
7 Correct 52 ms 5888 KB Output is correct
8 Partially correct 31 ms 2552 KB Output is partially correct
9 Partially correct 53 ms 7740 KB Output is partially correct
10 Correct 87 ms 13048 KB Output is correct
11 Correct 91 ms 13048 KB Output is correct
12 Correct 54 ms 6904 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 5 ms 1408 KB Output is correct
6 Correct 41 ms 3576 KB Output is correct
7 Correct 52 ms 5888 KB Output is correct
8 Partially correct 31 ms 2552 KB Output is partially correct
9 Partially correct 53 ms 7740 KB Output is partially correct
10 Correct 87 ms 13048 KB Output is correct
11 Correct 91 ms 13048 KB Output is correct
12 Correct 54 ms 6904 KB Output is correct
13 Execution timed out 1593 ms 118008 KB Time limit exceeded
14 Halted 0 ms 0 KB -