Submission #1106424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106424		cot7302	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	29 / 85	1477 ms	143180 KiB

necklace

#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;
}
 
using H = uint64_t;
 
mt19937_64 rng((uint64_t)time(0));
 
constexpr int kN = 3'000;
 
pair<H, int> hs[kN * (kN - 1) / 2];
 
bitset<kN> vis;
 
void solve() {
    auto st = clock();
    string S, T; cin >> S >> T;
    int n = size(S);
    int m = size(T);
    H bs = rng();
    while (bs % 2 == 0)
        bs = rng();
    int hc{};
    for (int i = 0; i < n; i++) {
        H h{};
        for (int j = i; j < n; j++) {
            h = h * bs + S[j];
            hs[hc++] = {h, i};
        }
    }
    sort(hs, hs + hc);
    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;
        H h{}, rh{}, pw{1};
        for (int i = id[t]; i < m; i++) {
            h = h * bs + T[i];
            rh = rh + T[i] * pw;
            for (int j = id[t]; j <= i; j++) {
                auto it = lower_bound(hs, hs + hc, pair{h, -1});
                if (i - id[t] + 1 > len && it != hs + hc && it->first == h)
                    len = i - id[t] + 1, ans = {it->second, id[t]}; 
                h -= pw * T[j];
                h *= bs;
                h += T[j];
            }
            for (int j = i; j >= id[t]; j--) {
                auto it = lower_bound(hs, hs + hc, pair{rh, -1});
                if (i - id[t] + 1 > len && it != hs + hc && it->first == rh)
                    len = i - id[t] + 1, ans = {it->second, id[t]}; 
                rh -= pw * T[j];
                rh *= bs;
                rh += T[j];
            }
            pw *= bs;
        }
    }
    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: 4 / 20
• Subtask 3: 0 / 40