Submission #953483

#	Time	Username	Problem	Language	Result	Execution time	Memory
953483		Rifal	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1541 ms	57944 KiB

selling_rna

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int N = 1e5 + 4;
vector<ll> v[N], v2[N];
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n, m; cin >> n >> m; string arr[n]; pair<string,string> arr2[m];
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int i = 0; i < m; i++) cin >> arr2[i].first >> arr2[i].second;
    for(int i = 0; i < n; i++) {
        ll cur = 1;
        v[i].push_back(0);
        v2[i].push_back(0);
        for(int j = 0; j < arr[i].size(); j++) {
            ll val;
            if(arr[i][j] == 'A') val = 0;
            else if(arr[i][j] == 'U')val = 1;
            else if(arr[i][j] == 'G')val = 2;
            else val = 3;

            val *= cur;
            val %= mod;
            val += v[i].back();
            val %= mod;
            v[i].push_back(val);
            cur *= P;
            cur %= mod;
        }
        cur = 1;
        for(int j = arr[i].size()-1; j >= 0; j--) {
            ll val;
            if(arr[i][j] == 'A') val = 0;
            else if(arr[i][j] == 'U')val = 1;
            else if(arr[i][j] == 'G')val = 2;
            else val = 3;

            val *= cur;
            val %= mod;
            val += v2[i].back();
            val %= mod;
            v2[i].push_back(val);
            cur *= P;
            cur %= mod;
        }
    }

    for(int i = 0; i < m; i++) {
        int cnt = 0;
        ll ans1 = 0; ll ans2 = 0;
        ll cur = 1;
        for(int j = 0; j < arr2[i].first.size(); j++) {
            ll val;
            if(arr2[i].first[j] == 'A') val = 0;
            else if(arr2[i].first[j] == 'U')val = 1;
            else if(arr2[i].first[j] == 'G')val = 2;
            else val = 3;

            val *= cur;
            val %= mod;
            ans1 += val;
            ans1 %= mod;
            cur *= P;
            cur %= mod;
        }
         cur = 1;
        for(int j = arr2[i].second.size()-1; j >= 0; j--) {
            ll val;
            if(arr2[i].second[j] == 'A') val = 0;
            else if(arr2[i].second[j] == 'U')val = 1;
            else if(arr2[i].second[j] == 'G')val = 2;
            else val = 3;

            val *= cur;
            val %= mod;
            ans2 += val;
            ans2 %= mod;
            cur *= P;
            cur %= mod;
        }
        int siz1 = arr2[i].first.size();
        int siz2 = arr2[i].second.size();
        for(int j = 0; j < n; j++) {
            if(siz1 < v[j].size() && siz2 < v2[j].size() && ans1 == v[j][siz1] && ans2 == v2[j][siz2]) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int j = 0; j < arr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
selling_rna.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j = 0; j < arr2[i].first.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             if(siz1 < v[j].size() && siz2 < v2[j].size() && ans1 == v[j][siz1] && ans2 == v2[j][siz2]) cnt++;
      |                ~~~~~^~~~~~~~~~~~~
selling_rna.cpp:96:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             if(siz1 < v[j].size() && siz2 < v2[j].size() && ans1 == v[j][siz1] && ans2 == v2[j][siz2]) cnt++;
      |                                      ~~~~~^~~~~~~~~~~~~~

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