oj.uz

Submission #1106430

# Submission time Handle Problem Language Result Execution time Memory
1106430 2024-10-30T10:30:42 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 82724 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.4 * 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 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 7 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 25 ms 884 KB Output is correct
7 Correct 46 ms 1632 KB Output is correct
8 Correct 222 ms 3168 KB Output is correct
9 Correct 359 ms 3336 KB Output is correct
10 Correct 481 ms 3424 KB Output is correct
11 Correct 519 ms 3424 KB Output is correct
12 Correct 346 ms 2912 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 25 ms 884 KB Output is correct
7 Correct 46 ms 1632 KB Output is correct
8 Correct 222 ms 3168 KB Output is correct
9 Correct 359 ms 3336 KB Output is correct
10 Correct 481 ms 3424 KB Output is correct
11 Correct 519 ms 3424 KB Output is correct
12 Correct 346 ms 2912 KB Output is correct
13 Execution timed out 1573 ms 82724 KB Time limit exceeded
14 Halted 0 ms 0 KB -