oj.uz

Submission #1106429

# Submission time Handle Problem Language Result Execution time Memory
1106429 2024-10-30T10:29:52 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 82884 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 764 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 7 ms 672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 764 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 26 ms 848 KB Output is correct
7 Correct 37 ms 1616 KB Output is correct
8 Correct 227 ms 3168 KB Output is correct
9 Correct 366 ms 3168 KB Output is correct
10 Correct 491 ms 3424 KB Output is correct
11 Correct 495 ms 3424 KB Output is correct
12 Correct 343 ms 3076 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 764 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 26 ms 848 KB Output is correct
7 Correct 37 ms 1616 KB Output is correct
8 Correct 227 ms 3168 KB Output is correct
9 Correct 366 ms 3168 KB Output is correct
10 Correct 491 ms 3424 KB Output is correct
11 Correct 495 ms 3424 KB Output is correct
12 Correct 343 ms 3076 KB Output is correct
13 Execution timed out 1551 ms 82884 KB Time limit exceeded
14 Halted 0 ms 0 KB -