oj.uz

Submission #1001751

# Submission time Handle Problem Language Result Execution time Memory
1001751 2024-06-19T07:29:54 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 805 ms 55324 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9
const int MAX = 1e4 + 5, MAX2 = 500 + 5, B = 61, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

int n, q;
string s;
string t[MAX];

map<pii, int> mp;
pii pre[MAX2];
int dp[MAX2][MAX2];
pii P[(int)5e5 + 5];
pii invP[(int)5e5 + 5];

int binpow(int a, int b, int m){
    if(b == 0) return 1;
    if(b & 1) return binpow(a, b - 1, m) % m * a % m;
    return binpow(a * a % m, b / 2, m) % m;
}
int inv(int a, int m){
    return binpow(a, m - 2, m);
}

pii calc(int l, int r){
    return {(pre[r].first - pre[l - 1].first + 2 * MOD1) % MOD1 * invP[l - 1].first % MOD1,
            (pre[r].second - pre[l - 1].second + 2 * MOD2) % MOD2 * invP[l - 1].second % MOD2};
}

void solve(){
    P[0]= {1, 1};
    invP[0] = {1, 1};
    for(int i = 1; i <= 5e5; i++){
        P[i].first = P[i - 1].first * B % MOD1;
        P[i].second = P[i - 1].second * B % MOD2;
        invP[i].first = invP[i - 1].first * inv(B, MOD1) % MOD1;
        invP[i].second = invP[i - 1].second * inv(B, MOD2) % MOD2;
    }
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        pii H = {0, 0};
        for(int j = 0; j < t[i].size(); j++){
            H.first = (H.first + (t[i][j] - 'a' + 1) * P[j].first % MOD1) % MOD1;
            H.second = (H.second + (t[i][j] - 'a' + 1) * P[j].second % MOD2) % MOD2;
            mp[H] = 1;
        }
    }
    cin >> s;
    int L = s.size();
    for(int i = 1; i <= L; i++){
        pre[i].first = (pre[i - 1].first + (s[i - 1] - 'a' + 1) * P[i - 1].first % MOD1) % MOD1;
        pre[i].second = (pre[i - 1].second + (s[i - 1] - 'a' + 1) * P[i - 1].second % MOD2) % MOD2;
    }
    for(int sz = 1; sz <= L; sz++){
        for(int i = 1; i + sz - 1 <= L; i++){
            int j = i + sz - 1;
            dp[i][j] = oo;
            if(mp.count(calc(i, j))){
                dp[i][j] = 1;
                continue;
            }
            for(int k = i; k <= j - 1; k++){
                dp[i][j] = min(dp[i][k] + dp[k + 1][j], dp[i][j]);
            }
        }
    }
    while(q--){
        int l, r; cin >> l >> r;
        l++;
        if(dp[l][r] == oo) dp[l][r] = -1;
        cout << dp[l][r] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:48:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 16412 KB Output is correct
2 Correct 622 ms 43664 KB Output is correct
3 Correct 559 ms 37944 KB Output is correct
4 Correct 676 ms 44580 KB Output is correct
5 Correct 619 ms 42800 KB Output is correct
6 Correct 716 ms 48976 KB Output is correct
7 Correct 805 ms 52052 KB Output is correct
8 Correct 736 ms 50488 KB Output is correct
9 Correct 701 ms 47696 KB Output is correct
10 Correct 511 ms 27476 KB Output is correct
11 Correct 662 ms 49084 KB Output is correct
12 Correct 480 ms 34188 KB Output is correct
13 Correct 544 ms 42528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 437 ms 55324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 16412 KB Output is correct
2 Correct 622 ms 43664 KB Output is correct
3 Correct 559 ms 37944 KB Output is correct
4 Correct 676 ms 44580 KB Output is correct
5 Correct 619 ms 42800 KB Output is correct
6 Correct 716 ms 48976 KB Output is correct
7 Correct 805 ms 52052 KB Output is correct
8 Correct 736 ms 50488 KB Output is correct
9 Correct 701 ms 47696 KB Output is correct
10 Correct 511 ms 27476 KB Output is correct
11 Correct 662 ms 49084 KB Output is correct
12 Correct 480 ms 34188 KB Output is correct
13 Correct 544 ms 42528 KB Output is correct
14 Runtime error 437 ms 55324 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -