oj.uz

Submission #1111666

# Submission time Handle Problem Language Result Execution time Memory
1111666 2024-11-12T14:06:58 Z Zero_OP Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 478616 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }

const int MAX = 1e5 + 5;
const int mod = 1e9 + random(7, 200);
const int base = 37;

int pw_base[MAX];

void preprocess(){
    pw_base[0] = 1;
    for(int i = 1; i < MAX; ++i){
        pw_base[i] = 1LL * pw_base[i - 1] * base % mod;
    }
}

int code(char c){
    if(c == 'A') return 3;
    if(c == 'G') return 7;
    if(c == 'C') return 17;
    if(c == 'U') return 23;
    assert(false);
}

int get_hash(const string& s){
    int h = 0;
    for(auto c : s)
        h = (1LL * h * base + code(c)) % mod;
    return h;
}

int get_hash(const string& s, int l, int r){
    int h = 0;
    for(int i = l; i <= r; ++i)
        h = (1LL * h * base + code(s[i])) % mod;
    return h;;
}

int get_hash(const vector<int>& h, int l, int r){
    ++r;
    int cur = h[r] - (1LL * h[l] * pw_base[r - l]) % mod;
    if(cur < 0) cur += mod;
    return cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    preprocess();

    int N, Q;
    cin >> N >> Q;

    vector<string> s(N);
    vector<int> sz(N);
    for(int i = 0; i < N; ++i) cin >> s[i], sz[i] = (int)s[i].size();

    vector<vector<int>> pref_hash(N);
    for(int i = 0; i < N; ++i){
        pref_hash[i].emplace_back(0);
        for(auto c : s[i]){
            pref_hash[i].emplace_back((1ll * pref_hash[i].back() * base + code(c)) % mod);
        }
    }

    const int B = 250;

    vector<int> vPref, vSuff;

    for(int i = 0; i < N; ++i){
        for(int j = 1; j <= min(sz[i], B); ++j){
            vPref.push_back(get_hash(pref_hash[i], 0, j - 1));
            vSuff.push_back(get_hash(pref_hash[i], sz[i] - j, sz[i] - 1));
        }
    }

    sort(vPref.begin(), vPref.end());
    vPref.erase(unique(vPref.begin(), vPref.end()), vPref.end());
    sort(vSuff.begin(), vSuff.end());
    vSuff.erase(unique(vSuff.begin(), vSuff.end()), vSuff.end());

    int vl = (int)vPref.size();
    vector<vector<int>> cnt(vl);

    vector<int> x, y;
    for(int i = 0; i < N; ++i){
        x.clear(); y.clear();
        for(int j = 0; j < min(B, sz[i]); ++j){
            int h1 = get_hash(pref_hash[i], 0, j);
            int p1 = lower_bound(vPref.begin(), vPref.end(), h1) - vPref.begin();
            x.push_back(p1);

            int h2 = get_hash(pref_hash[i], sz[i] - j - 1, sz[i] - 1);
            y.push_back(h2);
        }

        for(auto u : x){
            for(auto v : y){
                cnt[u].emplace_back(v);
            }
        }
    }

    for(int i = 0; i < vl; ++i){
        sort(cnt[i].begin(), cnt[i].end());
    }

    for(int _ = 0; _ < Q; ++_){
        string p, q;
        cin >> p >> q;

        if((int)p.size() <= B && (int)q.size() <= B){
            int hash_p = get_hash(p), hash_q = get_hash(q);
            if(!binary_search(vPref.begin(), vPref.end(), hash_p)){
                cout << 0 << '\n';
                continue;
            }

            int x = lower_bound(vPref.begin(), vPref.end(), hash_p) - vPref.begin();
            int res = upper_bound(cnt[x].begin(), cnt[x].end(), hash_q) - lower_bound(cnt[x].begin(), cnt[x].end(), hash_q);
            cout << res << '\n';
        } else{
            int cnt = 0, demand = max((int)p.size(), (int)q.size()), dl = (int)p.size(), dr = (int)q.size();
            int hash_p = get_hash(p), hash_q = get_hash(q);
            for(int i = 0; i < N; ++i){
                if(sz[i] >= demand){
                    if(get_hash(pref_hash[i], 0, dl - 1) == hash_p && get_hash(pref_hash[i], sz[i] - dr, sz[i] - 1) == hash_q){
                        ++cnt;
                    }
                }
            }

            cout << cnt << '\n';
        }
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 478616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8128 KB Output is correct
2 Correct 56 ms 8896 KB Output is correct
3 Correct 48 ms 8428 KB Output is correct
4 Correct 28 ms 7108 KB Output is correct
5 Correct 46 ms 8892 KB Output is correct
6 Correct 43 ms 8892 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Execution timed out 1586 ms 478616 KB Time limit exceeded
9 Halted 0 ms 0 KB -