oj.uz

Submission #972926

# Submission time Handle Problem Language Result Execution time Memory
972926 2024-05-01T10:27:09 Z duckindog Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 143 ms 120772 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100'000 + 10;
int n, m;
string str[N];
pair<string, string> Q[N];
 
int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
int nwt[N << 2][4];

int answer[N];
struct Trie {
  int it;
  vector<array<int, 4>> nwt;
  vector<int> id;
 
  void add(string s, int idx) {
    int g = 0;
    for (int i = 1; i <= (int)s.size(); ++i) {
      while (nwt.size() <= g) nwt.push_back(array<int, 4>());
 
      int path = convert(s[i - 1]);
      if (!nwt[g][path]) nwt[g][path] = ++it;
      g = nwt[g][path];
 
      while (id.size() <= it) id.push_back(false);
    }
    id[g] = idx;
  }
 
  void get(string s) { 
    int ret = 0;
    int g = 0;
    for (int i = 1; i <= (int)s.size(); ++i) {
      int path = convert(s[i - 1]);
      if (nwt.size() <= g || !nwt[g][path]) return;
      g = nwt[g][path];
      answer[id[g]] += 1;
    }
  }
} T[N << 2];
 
int it;
void add(const auto& s, const auto& e, int idx) { 
  int g = 0;
  for (int i = 1; i <= (int)s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
  }
  T[g].add(string(e.rbegin(), e.rend()), idx);
}
 
void get(const auto& s) { 
  string rs = string(s.rbegin(), s.rend());
  int g = 0;
  for (int i = 1; i <= (int)s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) return;
    g = nwt[g][path];
    T[g].get(rs);
  }
}

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) { 
    string s, e; cin >> s >> e;
    Q[i] = {s, e};
  }

  vector<pair<string, string>> que(Q + 1, Q + m + 1);
  sort(que.begin(), que.end());
  que.resize(unique(que.begin(), que.end()) - que.begin());

  {
    int it = 0;
    for (const auto& [s, e] : que) add(s, e, ++it);
    for (int i = 1; i <= n; ++i) get(str[i]);
  }

  for (int i = 1; i <= m; ++i) { 
    int idx = lower_bound(que.begin(), que.end(), Q[i]) - que.begin() + 1;
    cout << answer[idx] << "\n";
  }

}

Compilation message

selling_rna.cpp:12:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
      |                   ^~~~
selling_rna.cpp: In member function 'void Trie::add(std::string, int)':
selling_rna.cpp:24:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |       while (nwt.size() <= g) nwt.push_back(array<int, 4>());
      |              ~~~~~~~~~~~^~~~
selling_rna.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |       while (id.size() <= it) id.push_back(false);
      |              ~~~~~~~~~~^~~~~
selling_rna.cpp: In member function 'void Trie::get(std::string)':
selling_rna.cpp:40:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |       if (nwt.size() <= g || !nwt[g][path]) return;
      |           ~~~~~~~~~~~^~~~
selling_rna.cpp:36:9: warning: unused variable 'ret' [-Wunused-variable]
   36 |     int ret = 0;
      |         ^~~
selling_rna.cpp: At global scope:
selling_rna.cpp:48:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   48 | void add(const auto& s, const auto& e, int idx) {
      |                ^~~~
selling_rna.cpp:48:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   48 | void add(const auto& s, const auto& e, int idx) {
      |                               ^~~~
selling_rna.cpp:58:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   58 | void get(const auto& s) {
      |                ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34140 KB Output is correct
2 Correct 9 ms 34140 KB Output is correct
3 Correct 10 ms 34324 KB Output is correct
4 Correct 9 ms 34140 KB Output is correct
5 Correct 9 ms 34140 KB Output is correct
6 Correct 9 ms 34140 KB Output is correct
7 Correct 10 ms 34140 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 44372 KB Output is correct
2 Correct 132 ms 44920 KB Output is correct
3 Correct 45 ms 47156 KB Output is correct
4 Correct 44 ms 46900 KB Output is correct
5 Runtime error 81 ms 120772 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 38160 KB Output is correct
2 Correct 36 ms 36460 KB Output is correct
3 Correct 38 ms 37212 KB Output is correct
4 Correct 27 ms 36888 KB Output is correct
5 Correct 31 ms 36592 KB Output is correct
6 Correct 36 ms 37372 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34140 KB Output is correct
2 Correct 9 ms 34140 KB Output is correct
3 Correct 10 ms 34324 KB Output is correct
4 Correct 9 ms 34140 KB Output is correct
5 Correct 9 ms 34140 KB Output is correct
6 Correct 9 ms 34140 KB Output is correct
7 Correct 10 ms 34140 KB Output is correct
8 Correct 143 ms 44372 KB Output is correct
9 Correct 132 ms 44920 KB Output is correct
10 Correct 45 ms 47156 KB Output is correct
11 Correct 44 ms 46900 KB Output is correct
12 Runtime error 81 ms 120772 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -