oj.uz

Submission #332620

# Submission time Handle Problem Language Result Execution time Memory
332620 2020-12-03T01:37:13 Z casperwang Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 54764 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int MAXN = 100000;
const int MOD = 1000000007;
const int K = 880301;
int n, m;
string s[MAXN];
vector <int> pre_hash[MAXN];
vector <int> suf_hash[MAXN];
string p, q;
int now, ans;

bool pre(int a, int b, int len) {
  if (s[a].size() < len) return 0;
  return pre_hash[a][len-1] == b;
}

bool suf(int a, int b, int len) {
  if (s[a].size() < len) return 0;
  return suf_hash[a][len-1] == b;
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> s[i];
  sort(s, s+n);
  for (int i = 0; i < n; i++) {
    int h = 0;
    for (int j = 0; j < s[i].size(); j++) {
      h = (h * K + s[i][j]) % MOD;
      pre_hash[i].pb(h);
    }
    h = 0;
    for (int j = s[i].size()-1; j >= 0; j--) {
      h = (h * K + s[i][j]) % MOD;
      suf_hash[i].pb(h);
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> p >> q;
    int hp = 0;
    for (int j = 0; j < p.size(); j++)
      hp = (hp * K + p[j]) % MOD;
    int hq = 0;
    for (int j = q.size()-1; j >= 0; j--)
      hq = (hq * K + q[j]) % MOD;
    now = lower_bound(s, s+n, p) - s;
    ans = 0;
    while (now < n && pre(now, hp, p.size())) {
      if (suf(now, hq, q.size())) ans++;
      now++;
    }
    cout << ans << "\n";
  }
  return 0;
}

Compilation message

selling_rna.cpp: In function 'bool pre(long long int, long long int, long long int)':
selling_rna.cpp:17:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |   if (s[a].size() < len) return 0;
      |       ~~~~~~~~~~~~^~~~~
selling_rna.cpp: In function 'bool suf(long long int, long long int, long long int)':
selling_rna.cpp:22:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   22 |   if (s[a].size() < len) return 0;
      |       ~~~~~~~~~~~~^~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int j = 0; j < s[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~
selling_rna.cpp:47:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int j = 0; j < p.size(); j++)
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 49132 KB Output is correct
2 Correct 361 ms 53484 KB Output is correct
3 Correct 129 ms 51820 KB Output is correct
4 Correct 146 ms 54764 KB Output is correct
5 Correct 68 ms 36972 KB Output is correct
6 Correct 68 ms 37356 KB Output is correct
7 Correct 256 ms 42460 KB Output is correct
8 Correct 121 ms 51692 KB Output is correct
9 Correct 111 ms 52484 KB Output is correct
10 Correct 729 ms 52644 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8300 KB Output is correct
2 Correct 7 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 132 ms 49132 KB Output is correct
9 Correct 361 ms 53484 KB Output is correct
10 Correct 129 ms 51820 KB Output is correct
11 Correct 146 ms 54764 KB Output is correct
12 Correct 68 ms 36972 KB Output is correct
13 Correct 68 ms 37356 KB Output is correct
14 Correct 256 ms 42460 KB Output is correct
15 Correct 121 ms 51692 KB Output is correct
16 Correct 111 ms 52484 KB Output is correct
17 Correct 729 ms 52644 KB Output is correct
18 Execution timed out 1589 ms 11628 KB Time limit exceeded
19 Halted 0 ms 0 KB -