oj.uz

Submission #509827

# Submission time Handle Problem Language Result Execution time Memory
509827 2022-01-14T10:54:09 Z kianaRZV Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 78236 KB 
#include <bits/stdc++.h>
#define ui unsigned int
using namespace std;
const int maxn = 3e3 + 3;
const ui p = 31;
int n, m, ans, res1, res2;
ui  tav[maxn];
string s1, s2;
bool swaped;
map <ui, int> sub;

void mincycle(ui hsh, int l, int r) {
    int sz = r - l;
    sub[hsh] = l;
    for (int i = l; i < r - 1; i++) {
        hsh = hsh - tav[sz] * ((ui)(s1[i] - '`'));
        hsh = p * hsh + (ui)(s1[i] - '`');
        sub[hsh] = l;
    }
}

void read_input() {
    cin >> s1 >> s2;
    if(s1.size() > s2.size())
        swap(s1, s2), swaped = true;
    n = s1.size(), m = s2.size();
}

void solve() {
    tav[0] = 1;
    for(int i = 1; i < maxn; i++) {
        tav[i] = p * tav[i - 1];
    }
    for (int i = 0; i < n; i++) {
        ui hsh = 0;
        for (int j = i; j < n; j++) {
            hsh = hsh * p + (ui)(s1[j] - '`');
            mincycle(hsh, i, j);
        }
    }
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = p * h + (ui)(s2[j] - '`');
            if(sub.count(h)) {
                if(j - i + 1 > ans) {
                    ans = j - i + 1;
                    res1 = sub[h];
                    res2 = i;
                }
            }
        }
    }
    reverse(s2.begin(), s2.end());
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = p * h + (ui)(s2[j] - '`');
            if(sub.count(h)) {
                if(j - i + 1 > ans) {
                    ans = j - i + 1;
                    res1 = sub[h];
                    res2 = m - 1 - j;
                }
            }
        }
    }
    if(swaped)
        swap(res1, res2);
    cout << ans << '\n' << res1 << ' ' << res2;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    read_input(), solve();
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3896 KB Output is correct
2 Correct 32 ms 3520 KB Output is correct
3 Correct 12 ms 1404 KB Output is correct
4 Correct 22 ms 2960 KB Output is correct
5 Correct 61 ms 7368 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3896 KB Output is correct
2 Correct 32 ms 3520 KB Output is correct
3 Correct 12 ms 1404 KB Output is correct
4 Correct 22 ms 2960 KB Output is correct
5 Correct 61 ms 7368 KB Output is correct
6 Execution timed out 1581 ms 78236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3896 KB Output is correct
2 Correct 32 ms 3520 KB Output is correct
3 Correct 12 ms 1404 KB Output is correct
4 Correct 22 ms 2960 KB Output is correct
5 Correct 61 ms 7368 KB Output is correct
6 Execution timed out 1581 ms 78236 KB Time limit exceeded
7 Halted 0 ms 0 KB -