oj.uz

답안 #509818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
509818 2022-01-14T10:47:35 Z kianaRZV Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 25 ms 3896 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++) {
        int 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++) {
        int 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], res1 = i;
        }
    }
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < m; i++) {
        int 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], res1 = 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
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 3896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 3896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 3896 KB Output isn't correct
2 Halted 0 ms 0 KB -