Submission #474032

#	Time	Username	Problem	Language	Result	Execution time	Memory
474032		Lain	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1583 ms	55616 KiB

selling_rna

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
using namespace std;

const int S = 1024;
using bs = bitset<S>;

struct Trie {
  struct Node {
    Node* c[4];
    int idx;
    Node() {
      idx = -1;
      for (int i =0; i < 4; i++) c[i] = nullptr;
    }
  };

  Node* head;
  Trie() {
    head = new Node();
  }

  void insert(const string& s, int idx) {
    Node* curr = head;
    for (int i = 0; i < s.size(); i++){
      if (curr->c[s[i]-'A'] == nullptr)
        curr->c[s[i]-'A'] = new Node();
      curr = curr->c[s[i]-'A'];
    }
    curr->idx = idx;
  }

  void search(const string& s, int idx, vector<bs>& bits) {
    Node* curr = head;
    for (int i =0; i < s.size(); i++) {
      if (curr == nullptr) break;
      int j = s[i]-'A';
      if (curr->idx != -1)
        bits[curr->idx][idx] = 1;
      curr = curr->c[j];
    }
    if (curr != nullptr && curr->idx != -1)
      bits[curr->idx][idx] = 1;
  }
};


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  auto simplify = [&](string& s)->void {
    for (auto& x : s) {
      if (x=='G') x = 'B';
      else if (x=='U') x = 'D';
    }
  };

  int n,m;
  cin >> n >> m;
  vector<string> base(n);
  for (auto& x : base) {
    cin >> x;
    simplify(x);
  }
  vector<string> prefs(m), suffs(m);
  vector<bs> pref_bits, suff_bits;
  map<string,int> pref_need, suff_need;
  Trie pref_trie, suff_trie;
  for (int i =0; i < m; i++) {
    cin >> prefs[i] >> suffs[i];
    reverse(suffs[i].begin(),suffs[i].end());
    simplify(prefs[i]);
    simplify(suffs[i]);
    if (pref_need.count(prefs[i]) == 0) {
      pref_need[prefs[i]] = pref_bits.size();
      pref_bits.emplace_back();
      pref_trie.insert(prefs[i],pref_need[prefs[i]]);
    }
    if (suff_need.count(suffs[i]) == 0) {
      suff_need[suffs[i]] = suff_bits.size();
      suff_bits.emplace_back();
      suff_trie.insert(suffs[i],suff_need[suffs[i]]);
    }
  }
  vector<int> ans(m);
  for (int b = 0; b < n; b += S) {
    for (int i = b; i < min(b+S,n); i++) {
      pref_trie.search(base[i],i-b,pref_bits);
      reverse(base[i].begin(),base[i].end());
      suff_trie.search(base[i],i-b,suff_bits);
    }
    for (int i =0; i < m; i++)
      ans[i] += (pref_bits[pref_need[prefs[i]]]&suff_bits[suff_need[suffs[i]]]).count();
    for (auto& x : pref_bits) x.reset();
    for (auto& x : suff_bits) x.reset();
  }
  for (auto& x : ans) cout << x << '\n';
}
// Idea 1:
// Scan it by splitting it into sqrt(n) parts and then matching

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::insert(const string&, int)':
selling_rna.cpp:27:23: 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 i = 0; i < s.size(); i++){
      |                     ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::search(const string&, int, std::vector<std::bitset<1024> >&)':
selling_rna.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i =0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

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