oj.uz

Submission #155198

# Submission time Handle Problem Language Result Execution time Memory
155198 2019-09-27T05:37:19 Z dolphingarlic Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 224 ms 40316 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const ll P = 7, M = 1e9 + 9;
map<char, int> ALPHA = {{'A', 1}, {'G', 2}, {'U', 3}, {'C', 4}};

vector<ll> hsh[5000][2];
ll pw[100001];

ll make_hsh(string s) {
    ll hsh_val = 0;
    FOR(i, 0, s.size()) {
        hsh_val = (hsh_val + ALPHA[s[i]] * pw[i]) % M;
    }
    return hsh_val;
}

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

    pw[0] = 1;
    FOR(i, 1, 100001) pw[i] = (pw[i - 1] * P) % M;

    int n, q;
    cin >> n >> q;

    FOR(i, 0, n) {
        string s;
        cin >> s;
        ll hsh_val = 0;
        FOR(j, 0, s.size()) {
            hsh_val = (hsh_val + ALPHA[s[j]] * pw[j]) % M;
            hsh[i][0].push_back(hsh_val);
        }
        reverse(s.begin(), s.end());
        hsh_val = 0;
        FOR(j, 0, s.size()) {
            hsh_val = (hsh_val + ALPHA[s[j]] * pw[j]) % M;
            hsh[i][1].push_back(hsh_val);
        }
    }

    while (q--) {
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());
        ll hsh_a = make_hsh(a), hsh_b = make_hsh(b);

        int cnt = 0;
        FOR(i, 0, n) {
            if (hsh[i][0][a.size() - 1] == hsh_a && hsh[i][1][b.size() - 1] == hsh_b) cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'll make_hsh(std::__cxx11::string)':
selling_rna.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
selling_rna.cpp:14:9:
     FOR(i, 0, s.size()) {
         ~~~~~~~~~~~~~~                  
selling_rna.cpp:14:5: note: in expansion of macro 'FOR'
     FOR(i, 0, s.size()) {
     ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
selling_rna.cpp:34:13:
         FOR(j, 0, s.size()) {
             ~~~~~~~~~~~~~~              
selling_rna.cpp:34:9: note: in expansion of macro 'FOR'
         FOR(j, 0, s.size()) {
         ^~~
selling_rna.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
selling_rna.cpp:40:13:
         FOR(j, 0, s.size()) {
             ~~~~~~~~~~~~~~              
selling_rna.cpp:40:9: note: in expansion of macro 'FOR'
         FOR(j, 0, s.size()) {
         ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 40316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -