oj.uz

Submission #972554

# Submission time Handle Problem Language Result Execution time Memory
972554 2024-04-30T14:46:48 Z duckindog Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 78416 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10,
          base = 19973;
int n, m;
string str[N];
string st[N], ed[N];

using ull = unsigned long long;
ull pw[N];
struct Hash {
  int n;
  vector<ull> h;
 
  Hash() {}
  Hash(string s) : n(s.size()), h(s.size() + 1) { 
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
      h[i] = h[i - 1] * base + s[i - 1];
      pw[i] = pw[i - 1] * base;
    }
  }
  ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
} h[N];

int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
int nwt[N << 2][4];
vector<int> vt[N << 2];
bool mk[N << 2];

int it;
void mark(const auto& s) { 
  int g = 0;
  for (int i = 1; i <= s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
  }
  mk[g] = true;
}
void add(const auto& s, int id) { 
  int g = 0;
  for (int i = 1; i <= s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
    if (mk[g]) vt[g].push_back(id);
  }
}
int get(const auto& s, Hash e) { 
  int g = 0;
  for (int i = 1; i <= s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
  }

  int ret = 0;
  for (const auto& id : vt[g]) {
    if (h[id].n < e.n) continue;
    ret += (h[id].get(h[id].n - e.n + 1, h[id].n) == e.get(1, e.n));
  }
  return ret;
}



int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> str[i];
  for (int i = 1; i <= m; ++i) cin >> st[i] >> ed[i];

  for (int i = 1; i <= m; ++i) mark(st[i]);
  for (int i = 1; i <= n; ++i) { 
    h[i] = Hash(str[i]);
    add(str[i], i);
  }

  for (int i = 1; i <= m; ++i) cout << get(st[i], Hash(ed[i])) << "\n";
}

Compilation message

selling_rna.cpp:28:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
      |                   ^~~~
selling_rna.cpp:34:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   34 | void mark(const auto& s) {
      |                 ^~~~
selling_rna.cpp:43:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   43 | void add(const auto& s, int id) {
      |                ^~~~
selling_rna.cpp:52:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   52 | int get(const auto& s, Hash e) {
      |               ^~~~
selling_rna.cpp: In instantiation of 'void mark(const auto:24&) [with auto:24 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:77:42:   required from here
selling_rna.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'void add(const auto:25&, int) [with auto:25 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:80:18:   required from here
selling_rna.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'int get(const auto:26&, Hash) [with auto:26 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:83:62:   required from here
selling_rna.cpp:54:21: 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 i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 55380 KB Output is correct
2 Correct 128 ms 59216 KB Output is correct
3 Runtime error 47 ms 78416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25688 KB Output is correct
2 Correct 5 ms 25436 KB Output is correct
3 Correct 5 ms 25436 KB Output is correct
4 Correct 5 ms 25436 KB Output is correct
5 Correct 8 ms 25436 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 57 ms 55380 KB Output is correct
9 Correct 128 ms 59216 KB Output is correct
10 Runtime error 47 ms 78416 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -