oj.uz

Submission #1106424

# Submission time Handle Problem Language Result Execution time Memory
1106424 2024-10-30T10:25:38 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
29 / 85
 1477 ms 143180 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.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.0 / 25.0

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

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 548 KB Output is correct
2 Correct 16 ms 552 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 972 ms 2640 KB Output is correct
7 Partially correct 1472 ms 2684 KB Output is partially correct
8 Correct 1370 ms 2808 KB Output is correct
9 Correct 1471 ms 2684 KB Output is correct
10 Correct 1472 ms 2640 KB Output is correct
11 Partially correct 1477 ms 2640 KB Output is partially correct
12 Correct 1471 ms 2680 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 548 KB Output is correct
2 Correct 16 ms 552 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 23 ms 336 KB Output is correct
6 Correct 972 ms 2640 KB Output is correct
7 Partially correct 1472 ms 2684 KB Output is partially correct
8 Correct 1370 ms 2808 KB Output is correct
9 Correct 1471 ms 2684 KB Output is correct
10 Correct 1472 ms 2640 KB Output is correct
11 Partially correct 1477 ms 2640 KB Output is partially correct
12 Correct 1471 ms 2680 KB Output is correct
13 Runtime error 97 ms 143180 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -