oj.uz

Submission #1106423

# Submission time Handle Problem Language Result Execution time Memory
1106423 2024-10-30T10:22:34 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1411 ms 143416 KB 
#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.4 * 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 19 ms 516 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 19 ms 516 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 989 ms 2684 KB Output is correct
7 Correct 1406 ms 2692 KB Output is correct
8 Correct 1383 ms 2688 KB Output is correct
9 Correct 1411 ms 2696 KB Output is correct
10 Correct 1403 ms 2684 KB Output is correct
11 Correct 1407 ms 2684 KB Output is correct
12 Correct 1403 ms 2640 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 19 ms 516 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 989 ms 2684 KB Output is correct
7 Correct 1406 ms 2692 KB Output is correct
8 Correct 1383 ms 2688 KB Output is correct
9 Correct 1411 ms 2696 KB Output is correct
10 Correct 1403 ms 2684 KB Output is correct
11 Correct 1407 ms 2684 KB Output is correct
12 Correct 1403 ms 2640 KB Output is correct
13 Runtime error 105 ms 143416 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -