oj.uz

Submission #509830

# Submission time Handle Problem Language Result Execution time Memory
509830 2022-01-14T10:56:15 Z kianaRZV Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 78660 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 hsh = 0;
        for (int j = i; j < m; j++) {
            hsh = p * hsh + (ui)(s2[j] - '`');
            if (sub.count(hsh))
                if (j - i + 1 > ans)
                    ans = j - i + 1, res1 = sub[hsh], res2 = i;
        }
    }
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < m; i++) {
        ui hsh = 0;
        for (int j = i; j < m; j++) {
            hsh = p * hsh + (ui)(s2[j] - '`');
            if (sub.count(hsh))
                if (j - i + 1 > ans)
                    ans = j - i + 1, res1 = sub[hsh], res2 = m - j - 1;
        }
    }
    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 25 ms 3916 KB Output is correct
2 Correct 29 ms 3532 KB Output is correct
3 Correct 13 ms 1344 KB Output is correct
4 Correct 22 ms 3012 KB Output is correct
5 Correct 55 ms 7272 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3916 KB Output is correct
2 Correct 29 ms 3532 KB Output is correct
3 Correct 13 ms 1344 KB Output is correct
4 Correct 22 ms 3012 KB Output is correct
5 Correct 55 ms 7272 KB Output is correct
6 Execution timed out 1590 ms 78660 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3916 KB Output is correct
2 Correct 29 ms 3532 KB Output is correct
3 Correct 13 ms 1344 KB Output is correct
4 Correct 22 ms 3012 KB Output is correct
5 Correct 55 ms 7272 KB Output is correct
6 Execution timed out 1590 ms 78660 KB Time limit exceeded
7 Halted 0 ms 0 KB -