제출 #1224170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224170		omsincoconut	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	9 / 85	1595 ms	692 KiB

necklace

#include <iostream>
#include <string.h>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef __int128 ll;

const int MAXN = 3e3+100;

const ll MOD = 2'305'843'009'213'693'951, BASE = 271, INV = 663674371655601949;

ll pw[MAXN], invpw[MAXN];

void init() {
    pw[0] = invpw[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pw[i] = (pw[i-1]*BASE)%MOD;
        invpw[i] = (invpw[i-1]*INV)%MOD;
    }
}

ll hashchar(char c) {
    return ((c-'a')+55)^73;
}

pair<int, int> check(string &s, string &t, int k) {
    int n = s.size()-2, m = t.size()-2;

    ll sq[n+1], tq[m+1];
    sq[0] = tq[0] = 0;

    for (int i = 1; i <= n; i++) {
        sq[i] = (sq[i-1] + pw[i]*hashchar(s[i]))%MOD;
    }

    for (int i = 1; i <= m; i++) {
        tq[i] = (tq[i-1] + pw[i]*hashchar(t[i]))%MOD;
    }

    unordered_map<long long, int> dt;
    for (int i = 0; i+k <= n; i++) {
        ll val = (sq[i+k]-sq[i]+MOD)%MOD*invpw[i+1]%MOD;
        dt[val] = i;
    }

    for (int i = 0; i+k <= m; i++) {
        ll val = (tq[i+k]-tq[i]+MOD)%MOD*invpw[i+1]%MOD;
        for (int j = 1; j <= k; j++) {
            if (dt.count(val)) return {dt[val], i};
            val = (val-hashchar(t[i+j])+MOD)%MOD;
            val = (val*invpw[1])%MOD;
            val = (val+pw[k-1]*hashchar(t[i+j]))%MOD;
        }
    }

    return {-1, -1};
}

tuple<int, int, int> answer(string &s, string &t) {
    int l = 0, r = min(s.size()-1, t.size()-1);
    pair<int, int> ans[min(s.size(), t.size())];
    while (r-l > 1) {
        int mid = (l+r)>>1;
        pair<int, int> checked = check(s, t, mid);
        
        if (checked != make_pair(-1, -1)) {
            l = mid;
            ans[l] = checked;
        } else r = mid;
    }

    return make_tuple(l, ans[l].first, ans[l].second);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init();

    string s, t;
    cin >> s >> t;
    s = '.'+s+'.';
    t = '.'+t+'.';

    tuple<int, int, int> answers[5];

    answers[1] = answer(s, t);
    reverse(s.begin(), s.end());
    answers[2] = answer(s, t);
    reverse(s.begin(), s.end());

    reverse(t.begin(), t.end());
    answers[3] = answer(s, t);
    reverse(s.begin(), s.end());
    answers[4] = answer(s, t);
    reverse(s.begin(), s.end());

    answers[2] = make_tuple(get<0>(answers[2]), s.size()-get<0>(answers[2])-get<1>(answers[2])-2, get<2>(answers[2]));
    answers[3] = make_tuple(get<0>(answers[3]), get<1>(answers[3]), t.size()-get<0>(answers[3])-get<2>(answers[3])-2);
    answers[4] = make_tuple(get<0>(answers[4]), s.size()-get<0>(answers[4])-get<1>(answers[4])-2, t.size()-get<0>(answers[4])-get<2>(answers[4])-2);

    tuple<int, int, int> fin = *max_element(answers+1, answers+5);

    cout << get<0>(fin) << '\n' << get<1>(fin) << ' ' << get<2>(fin);

    return 0;
}

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 0 / 40