oj.uz

Submission #1106431

# Submission time Handle Problem Language Result Execution time Memory
1106431 2024-10-30T10:31:17 Z cot7302 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 4612 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];
    };
    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++) {
        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();
}

Compilation message

necklace.cpp: In function 'void solve()':
necklace.cpp:25:10: warning: unused variable 'st' [-Wunused-variable]
   25 |     auto st = clock();
      |          ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 8 ms 592 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 26 ms 592 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 8 ms 592 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 26 ms 592 KB Output is correct
6 Correct 168 ms 1272 KB Output is correct
7 Correct 256 ms 2128 KB Output is correct
8 Execution timed out 1581 ms 4612 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 8 ms 592 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 26 ms 592 KB Output is correct
6 Correct 168 ms 1272 KB Output is correct
7 Correct 256 ms 2128 KB Output is correct
8 Execution timed out 1581 ms 4612 KB Time limit exceeded
9 Halted 0 ms 0 KB -