Submission #1106429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106429		cot7302	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	45 / 85	1551 ms	82884 KiB

necklace

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

mt19937_64 rng((uint64_t)time(0));

constexpr int kN = 3'000;

using Hs = uint64_t;

Hs hs[2][kN + 2], pw[kN + 1];

void solve() {
    auto st = clock();
    string S, T; cin >> S >> T;
    int n = size(S);
    int m = size(T);
    bool fl = false;
    if (n < m)
        swap(n, m), swap(S, T), fl = true;
    Hs bs{};
    for (auto x = rng(); (bs = x, x) % 2 == 0; )
        x = rng();
    pw[0] = 1;
    for (int i = 0; i < m; i++) {
        pw[i + 1] = pw[i] * bs;
        hs[0][i + 1] = hs[0][i] * bs + T[i];
    }
    for (int i = m - 1; i >= 0; i--) {
        hs[1][i] = hs[1][i + 1] * bs + T[i];
    }
    auto get_0 = [&](int l, int r) -> Hs {
        return hs[0][r] - hs[0][l] * pw[r - l];
    };
    auto get_1 = [&](int l, int r) -> Hs {
        return hs[1][l] - hs[1][r] * pw[r - l];
    };
    unordered_map<Hs, int> mp;
    for (int i = 0; i < n; i++) {
        Hs h{};
        for (int j = i; j < n; j++) {
            h = h * bs + S[j];
            mp[h] = i;
        }
    }
    vec<int> id(m);
    iota(ALL(id), 0);
    shuffle(ALL(id), rng);
    int len{};
    pair<int, int> ans{};
    for (int t = 0; t < m; t++) {
        if (clock() - st >= 1.47 * CLOCKS_PER_SEC)
            break;
        for (int i = m - 1; i >= id[t]; i--) {
            if (i - id[t] + 1 <= len) break;
            Hs h = get_0(id[t], i + 1);
            Hs r = get_1(id[t], i + 1);
            bool f = false;
            Hs p = pw[i - id[t]];
            for (int j = id[t]; j <= i; j++) {
                if (i - id[t] + 1 > len) {
                    auto it = mp.find(h);
                    if (it != end(mp)) {
                        len = i - id[t] + 1, ans = {it->second, id[t]};
                        f = true;
                        break;
                    }
                }
                h -= p * T[j];
                h *= bs;
                h += T[j];
            }
            if (f) break;
            for (int j = i; j >= id[t]; j--) {
                if (i - id[t] + 1 > len) {
                    auto it = mp.find(r);
                    if (it != end(mp)) {
                        len = i - id[t] + 1, ans = {it->second, id[t]};
                        f = true;
                        break;
                    }
                }
                r -= p * T[j];
                r *= bs;
                r += T[j];
            }
            if (f) break;
        }
    }
    if (fl)
        swap(ans.first, ans.second);
    cout << len << '\n';
    cout << ans.first << ' ' << ans.second << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

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