oj.uz

답안 #319668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319668 2020-11-06T05:02:39 Z qpwoeirut Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 168380 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)((x).size())

typedef long long ll;

const int MN = 100001;
const int CT = 2;
const ll MOD[CT] = {(ll)1e9 + 7, (ll)1e9+9};
const ll BASE = 11;

int to_int[128];

struct Hash {
    ll h[CT];

    Hash() {
        fill(h, h+CT, 0);
    }
    Hash(const string& s) {
        fill(h, h+CT, 0);
        for (int i=sz(s) - 1; i>=0; --i) {
            for (int j=0; j<CT; ++j) {
                h[j] = ((h[j] * BASE) + to_int[s[i]]) % MOD[j];
            }
        }
    }
    void add(const char& c) {
        for (int i=0; i<CT; ++i) {
            h[i] = ((h[i] * BASE) + to_int[c]) % MOD[i];
        }
    }
    inline const bool operator<(const Hash& other) const {
        for (int i=0; i<CT; ++i) {
            if (h[i] != other.h[i]) {
                return h[i] < other.h[i];
            }
        }
        return false;
    }
    inline const bool operator==(const Hash& other) const {
        for (int i=0; i<CT; ++i) {
            if (h[i] != other.h[i]) return false;
        }
        return true;
    }
};

struct Str {
    string s;
    vector<Hash> h;

    Str() {
        s = "";
        h = vector<Hash>();
    }
    void make_hashes() {
        h = vector<Hash>(sz(s));
        for (int i=0; i<sz(s); ++i) {
            if (i) h[i] = h[i-1];
            h[i].add(s[i]);
        }
    }
    int size() {
        return s.size();
    }
    inline const bool operator<(const Str& other) {
        int mn = min(sz(s), sz(other.s));
        int lo = 0, hi = mn; 
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (h[mid] == other.h[mid]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        if (lo == mn) {
            return sz(s) < sz(other.s);
        }
        return s[lo] < other.s[lo];
    }
};

int N, M;
Str S[MN];
map<Hash, vector<int>> shash;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    to_int['A'] = 1;
    to_int['B'] = 2;
    to_int['C'] = 3;
    to_int['D'] = 4;
    to_int['G'] = 5;
    to_int['H'] = 6;
    to_int['U'] = 7;
    to_int['V'] = 8;

    cin >> N >> M;
    for (int i=0; i<N; ++i) {
        cin >> S[i].s;
        S[i].make_hashes();
    }
    sort(S, S+N);

    for (int i=0; i<N; ++i) {
        Hash cur;
        for (int j=sz(S[i]) - 1; j>=0; --j) {
            cur.add(S[i].s[j]);
            shash[cur].emplace_back(i);
        }
    }

    for (int i=0; i<M; ++i) {
        Str P;
        string Q;
        cin >> P.s >> Q;
        P.make_hashes();

        int lo = lower_bound(S, S+N, P) - S;
        P.s.back()++;
        P.make_hashes();
        int hi = lower_bound(S+lo, S+N, P) - S;

        Hash suff(Q);
        auto it = shash.find(suff);
        if (it == shash.end()) {
            cout << "0\n";
        } else {
            int ans = lower_bound(it->second.begin(), it->second.end(), hi) - lower_bound(it->second.begin(), it->second.end(), lo);
            cout << ans << '\n';
        }
    }
}
/*
2 3
AUGC
AGC
G C
AU C
A C

3 3
AA
AA AGA
AA AA
AG GA
AG GA

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

Compilation message

selling_rna.cpp: In constructor 'Hash::Hash(const string&)':
selling_rna.cpp:26:52: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |                 h[j] = ((h[j] * BASE) + to_int[s[i]]) % MOD[j];
      |                                                    ^
selling_rna.cpp: In member function 'void Hash::add(const char&)':
selling_rna.cpp:32:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |             h[i] = ((h[i] * BASE) + to_int[c]) % MOD[i];
      |                                            ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 5 ms 5888 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 5 ms 5888 KB Output is correct
5 Correct 5 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 5 ms 5868 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1582 ms 168380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 9076 KB Output is correct
2 Correct 58 ms 8952 KB Output is correct
3 Correct 66 ms 9060 KB Output is correct
4 Correct 52 ms 8676 KB Output is correct
5 Correct 58 ms 8676 KB Output is correct
6 Correct 71 ms 8808 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 5 ms 5888 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Correct 5 ms 5888 KB Output is correct
5 Correct 5 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 5 ms 5868 KB Output is correct
8 Execution timed out 1582 ms 168380 KB Time limit exceeded
9 Halted 0 ms 0 KB -