Submission #155199

#	Time	Username	Problem	Language	Result	Execution time	Memory
155199		dolphingarlic	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1564 ms	45640 KiB

selling_rna

#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[100001][2];
ll pw[200001];

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, 200001) 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 (stderr)

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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40