oj.uz

Submission #953483

# Submission time Handle Problem Language Result Execution time Memory
953483 2024-03-26T03:15:03 Z Rifal Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 57944 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5148 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 52368 KB Output is correct
2 Correct 253 ms 56936 KB Output is correct
3 Correct 148 ms 55100 KB Output is correct
4 Correct 225 ms 57004 KB Output is correct
5 Correct 202 ms 37160 KB Output is correct
6 Correct 244 ms 37724 KB Output is correct
7 Correct 139 ms 48076 KB Output is correct
8 Correct 261 ms 57912 KB Output is correct
9 Correct 239 ms 57944 KB Output is correct
10 Correct 467 ms 52920 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1541 ms 15240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5148 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 94 ms 52368 KB Output is correct
9 Correct 253 ms 56936 KB Output is correct
10 Correct 148 ms 55100 KB Output is correct
11 Correct 225 ms 57004 KB Output is correct
12 Correct 202 ms 37160 KB Output is correct
13 Correct 244 ms 37724 KB Output is correct
14 Correct 139 ms 48076 KB Output is correct
15 Correct 261 ms 57912 KB Output is correct
16 Correct 239 ms 57944 KB Output is correct
17 Correct 467 ms 52920 KB Output is correct
18 Execution timed out 1541 ms 15240 KB Time limit exceeded
19 Halted 0 ms 0 KB -