Submission #839441

#	Time	Username	Problem	Language	Result	Execution time	Memory
839441		socpite	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1577 ms	211024 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 2207;
const int base = 31;
const int sqr = 1300;

int n, q;

int cnt[maxn];

struct hashsus
{
    long long operator()(const pair<int, int> &a) const
    {
        return 1LL * mod * a.first + a.second;
    }
};

unordered_map<int, vector<int>> mp[2];
unordered_map<pair<int, int>, int, hashsus> mpq;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    string str;
    for (int i = 1; i <= n; i++)
    {
        cin >> str;
        if (str.size() >= sqr)
        {
            int val = 0;
            for (int j = 0; j < str.size(); j++)
            {
                auto v = str[j];
                val = (1LL * val * base + (v - 'A' + 1)) % mod;
                mp[0][val].push_back(i);
            }
            val = 0;
            for (int j = str.size() - 1; j >= 0; j--)
            {
                auto v = str[j];
                val = (1LL * val * base + (v - 'A' + 1)) % mod;
                mp[1][val].push_back(i);
            }
        }
        else
        {
            int pfx = 0;
            for (int j = 0; j < str.size(); j++)
            {
                pfx = (1LL * pfx * base + (str[j] - 'A' + 1)) % mod;
                int sfx = 0;
                for (int k = str.size() - 1; k >= 0; k--)
                {
                    sfx = (1LL * sfx * base + (str[k] - 'A' + 1)) % mod;
                    mpq[{pfx, sfx}]++;
                }
            }
        }
    }
    string P, Q;
    while (q--)
    {
        int pfx = 0, sfx = 0;
        cin >> P >> Q;
        for (int i = 0; i < P.size(); i++)
        {
            pfx = (1LL * pfx * base + P[i] - 'A' + 1) % mod;
        }
        for (int i = Q.size() - 1; i >= 0; i--)
        {
            sfx = (1LL * sfx * base + Q[i] - 'A' + 1) % mod;
        }
        vector<int> v1 = mp[0][pfx], v2 = mp[1][sfx];
        assert(v1.size() <= sqr);
        int ans = mpq[{pfx, sfx}];
        for (auto v : v1)
            cnt[v]++;
        for (auto v : v2)
            cnt[v]++;
        for (auto v : v1)
        {
            ans += (cnt[v] == 2);
        }
        for (auto v : v1)
            cnt[v]--;
        for (auto v : v2)
            cnt[v]--;
        cout << ans << "\n";
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j = 0; j < str.size(); j++)
      |                             ~~^~~~~~~~~~~~
selling_rna.cpp:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int j = 0; j < str.size(); j++)
      |                             ~~^~~~~~~~~~~~
selling_rna.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < P.size(); i++)
      |                         ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40