oj.uz

Submission #880879

# Submission time Handle Problem Language Result Execution time Memory
880879 2023-11-30T07:58:17 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 1500 ms 305448 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pb push_back
#define pii array<int, 2>
#define piii array<int, 3>

int power(int a, ll b, int mod) {
    int ret = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1)
            ret = 1ll * ret * a % mod;
    return ret;
}

const int N = 3e3 + 4;
const int P = 701, M[] = {(int) 1e9 + 7, (int) 1e9 + 9};
const int inv[] = {power(P, M[0] - 2, M[0]), power(P, M[1] - 2, M[1])};

int n[2], pw[N][2];
string s[2];

pii check(int sz) {
    vector<piii> hashes[2];
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j + sz - 1 < n[i]; ++j) {
            pii h = {0, 0};
            for (int k = j; k < j + sz; ++k) {
                for (int o = 0; o < 2; ++o) { 
                    h[o] = (h[o] + 1ll * s[i][k] * pw[k - j][o] % M[o]) % M[o];
                }
            }

            hashes[i].pb({h[0], h[1], j});
            for (int k = j + 1; k < j + sz; ++k) {
                for (int o = 0; o < 2; ++o) {
                    h[o] = (h[o] - s[i][k - 1] + M[o]) % M[o];
                    h[o] = 1ll * h[o] * inv[o] % M[o];
                    h[o] = (h[o] + 1ll * s[i][k - 1] * pw[sz - 1][o] % M[o]) % M[o];
                    hashes[i].pb({h[0], h[1], j});
                }
            }
        }
    }
    for (int i = 0; i < 2; ++i) {
        reverse(s[i].begin(), s[i].end());
    }

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j + sz - 1 < n[i]; ++j) {
            pii h = {0, 0};
            for (int k = j; k < j + sz; ++k) {
                for (int o = 0; o < 2; ++o) { 
                    h[o] = (h[o] + 1ll * s[i][k] * pw[k - j][o] % M[o]) % M[o];
                }
            }

            int t = j + sz - 1;
            hashes[i].pb({h[0], h[1], n[i] - t - 1});
            for (int k = j + 1; k < j + sz; ++k) {
                for (int o = 0; o < 2; ++o) {
                    h[o] = (h[o] - s[i][k - 1] + M[o]) % M[o];
                    h[o] = 1ll * h[o] * inv[o] % M[o];
                    h[o] = (h[o] + 1ll * s[i][k - 1] * pw[sz - 1][o] % M[o]) % M[o];
                    hashes[i].pb({h[0], h[1], n[i] - t - 1});
                }
            }
        }
    }
    for (int i = 0; i < 2; ++i) {
        reverse(s[i].begin(), s[i].end());
        sort(hashes[i].begin(), hashes[i].end());
    }

    int pt = 0;
    for (auto [h0, h1, idx] : hashes[0]) {
        while (h0 > hashes[1][pt][0]) {
            ++pt;
            if (pt == hashes[1].size()) {
                return {-1, -1};
            }
        }
        if (hashes[1][pt][0] == h0) {
            while (h0 == hashes[1][pt][0]) {
                if (h0 == hashes[1][pt][0] && h1 == hashes[1][pt][1]) {
                    return {idx, hashes[1][pt][2]};
                }
                ++pt;
                if (pt == hashes[1].size()) {
                    return {-1, -1};
                }
            }
        }
    }
    return {-1, -1};
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    pw[0][0] = pw[0][1] = 1;
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < 2; ++j) {
            pw[i][j] = 1ll * pw[i - 1][j] * P % M[j];
        }
    }

    cin >> s[0] >> s[1];
    n[0] = s[0].size();
    n[1] = s[1].size();
    
    int l = 0, r = min(n[0], n[1]) + 1, m;
    while (r - l > 1) {
        m = (l + r) / 2;
        pii res = check(m);
        if (res[0] != -1) {
            l = m;
        }
        else {
            r = m;
        }
    }

    cout << l << '\n';
    pii ans = check(l);
    cout << ans[0] << ' ' << ans[1];

    return 0;
}

Compilation message

necklace.cpp: In function 'std::array<int, 2> check(int)':
necklace.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             if (pt == hashes[1].size()) {
      |                 ~~~^~~~~~~~~~~~~~~~~~~
necklace.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 if (pt == hashes[1].size()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB Output is correct
2 Partially correct 11 ms 860 KB Output is partially correct
3 Correct 13 ms 992 KB Output is correct
4 Partially correct 11 ms 776 KB Output is partially correct
5 Correct 7 ms 860 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB Output is correct
2 Partially correct 11 ms 860 KB Output is partially correct
3 Correct 13 ms 992 KB Output is correct
4 Partially correct 11 ms 776 KB Output is partially correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 204 ms 6480 KB Output is correct
7 Partially correct 311 ms 8800 KB Output is partially correct
8 Correct 319 ms 5636 KB Output is correct
9 Partially correct 269 ms 9604 KB Output is partially correct
10 Partially correct 189 ms 5756 KB Output is partially correct
11 Partially correct 140 ms 5972 KB Output is partially correct
12 Correct 302 ms 8304 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB Output is correct
2 Partially correct 11 ms 860 KB Output is partially correct
3 Correct 13 ms 992 KB Output is correct
4 Partially correct 11 ms 776 KB Output is partially correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 204 ms 6480 KB Output is correct
7 Partially correct 311 ms 8800 KB Output is partially correct
8 Correct 319 ms 5636 KB Output is correct
9 Partially correct 269 ms 9604 KB Output is partially correct
10 Partially correct 189 ms 5756 KB Output is partially correct
11 Partially correct 140 ms 5972 KB Output is partially correct
12 Correct 302 ms 8304 KB Output is correct
13 Execution timed out 1549 ms 305448 KB Time limit exceeded
14 Halted 0 ms 0 KB -