oj.uz

Submission #446608

# Submission time Handle Problem Language Result Execution time Memory
446608 2021-07-22T17:28:08 Z Mamedov Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 96532 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;


const int up = 3003;
const ui base = 31;
const int mod = 2100003007;

unordered_map<ui, int>SubHash;

ui pw[up];

void preClc() {
    pw[0] = 1;
    for(int i = 1; i < up; ++i) {
        pw[i] = base * pw[i - 1];
    }
}

string a, b;
int res = 0;
int sa = 0, sb = 0;

void CyclicHashs(ui h, int l, int r) {
    if(SubHash.count(h)) {
        if(res < r - l + 1) {
            res = r - l + 1;
            sa = l;
            sb = SubHash[h];
        }
    }
    for(int i = l; i < r - 1; ++i) {
        h = h - pw[r - l] * (a[i] - '`');
        h = base * h + (a[i] - '`');
        if(SubHash.count(h)) {
            if(res < r - l + 1) {
                res = r - l + 1;
                sa = l;
                sb = SubHash[h];
            }
        }
    }
}
void solve() {
    preClc();
    int n, m;
    cin >> a >> b;

    bool swaped = false;
    if(a.size() > b.size()) {
        swap(a, b);
        swaped = true;
    }

    n = (int)a.size();
    m = (int)b.size();

    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (b[j] - '`');
            SubHash[h] = i;
        }
    }
    reverse(b.begin(), b.end());
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (b[j] - '`');
            SubHash[h] = m - 1 - j;
        }
    }

    for(int i = 0; i < n; ++i) {
        ui h = 0;
        for(int j = i; j < n; ++j) {
            h = base * h + (a[j] - '`');
            CyclicHashs(h, i, j);
        }
    }

    if(swaped) {
        swap(sa, sb);
    }
    cout << res << '\n';
    cout << sa << ' ' << sb << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 9 ms 716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 356 ms 2544 KB Output is correct
7 Correct 516 ms 3200 KB Output is correct
8 Correct 413 ms 5816 KB Output is correct
9 Correct 782 ms 5952 KB Output is correct
10 Correct 753 ms 6436 KB Output is correct
11 Correct 751 ms 6428 KB Output is correct
12 Correct 609 ms 5520 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 356 ms 2544 KB Output is correct
7 Correct 516 ms 3200 KB Output is correct
8 Correct 413 ms 5816 KB Output is correct
9 Correct 782 ms 5952 KB Output is correct
10 Correct 753 ms 6436 KB Output is correct
11 Correct 751 ms 6428 KB Output is correct
12 Correct 609 ms 5520 KB Output is correct
13 Execution timed out 1595 ms 96532 KB Time limit exceeded
14 Halted 0 ms 0 KB -