oj.uz

Submission #880880

# Submission time Handle Problem Language Result Execution time Memory
880880 2023-11-30T08:00:19 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 1500 ms 305264 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 = 229939, 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 13 ms 856 KB Output is correct
2 Partially correct 13 ms 956 KB Output is partially correct
3 Correct 12 ms 916 KB Output is correct
4 Partially correct 11 ms 800 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 13 ms 856 KB Output is correct
2 Partially correct 13 ms 956 KB Output is partially correct
3 Correct 12 ms 916 KB Output is correct
4 Partially correct 11 ms 800 KB Output is partially correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 194 ms 6436 KB Output is correct
7 Partially correct 314 ms 8840 KB Output is partially correct
8 Correct 314 ms 5280 KB Output is correct
9 Partially correct 269 ms 9496 KB Output is partially correct
10 Partially correct 193 ms 6092 KB Output is partially correct
11 Partially correct 142 ms 5716 KB Output is partially correct
12 Correct 298 ms 9812 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 856 KB Output is correct
2 Partially correct 13 ms 956 KB Output is partially correct
3 Correct 12 ms 916 KB Output is correct
4 Partially correct 11 ms 800 KB Output is partially correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 194 ms 6436 KB Output is correct
7 Partially correct 314 ms 8840 KB Output is partially correct
8 Correct 314 ms 5280 KB Output is correct
9 Partially correct 269 ms 9496 KB Output is partially correct
10 Partially correct 193 ms 6092 KB Output is partially correct
11 Partially correct 142 ms 5716 KB Output is partially correct
12 Correct 298 ms 9812 KB Output is correct
13 Execution timed out 1541 ms 305264 KB Time limit exceeded
14 Halted 0 ms 0 KB -