oj.uz

Submission #1106428

# Submission time Handle Problem Language Result Execution time Memory
1106428 2024-10-30T10:28:36 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
29 / 85
 1500 ms 72456 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)];
 
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 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 22 ms 540 KB Output is correct

Subtask #2
4.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 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 22 ms 540 KB Output is correct
6 Correct 972 ms 2640 KB Output is correct
7 Correct 1409 ms 2640 KB Output is correct
8 Correct 1355 ms 2684 KB Output is correct
9 Correct 1406 ms 2680 KB Output is correct
10 Correct 1407 ms 2640 KB Output is correct
11 Correct 1407 ms 2676 KB Output is correct
12 Partially correct 1406 ms 2680 KB Output is partially 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 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 22 ms 540 KB Output is correct
6 Correct 972 ms 2640 KB Output is correct
7 Correct 1409 ms 2640 KB Output is correct
8 Correct 1355 ms 2684 KB Output is correct
9 Correct 1406 ms 2680 KB Output is correct
10 Correct 1407 ms 2640 KB Output is correct
11 Correct 1407 ms 2676 KB Output is correct
12 Partially correct 1406 ms 2680 KB Output is partially correct
13 Execution timed out 1558 ms 72456 KB Time limit exceeded
14 Halted 0 ms 0 KB -