oj.uz

Submission #1074711

# Submission time Handle Problem Language Result Execution time Memory
1074711 2024-08-25T13:10:24 Z nima_aryan Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 26 ms 17492 KB 
#include <bits/stdc++.h>

using namespace std;

vector<char> alpha{'A', 'C', 'G', 'U'};

string next(string& s) {
  int n = s.size();
  for (int i = n - 1; i >= 0; --i) {
    for (int x = 0; x < 3; ++x) {
      if (s[i] == alpha[x]) {
        s[i] = alpha[x + 1];
        return s;
      }
    }
    s.pop_back();
  }
  return string(n, 'Z');
}

constexpr int N = 2.1E5;
vector<array<int, 4>> trie(N);
vector<int> cnt(N);
int tot = 1;

void insert(const string& s) {
  int p = 1;
  for (int i = 0; i < s.size(); ++i) {
    int& q = trie[p][s[i] - 'A'];
    if (!q) {
      q = ++tot;
    }
    ++cnt[p = q];
  }
}
int count(const string& s) {
  int p = 1;
  for (int i = 0; i < s.size(); ++i) {
    int q = trie[p][s[i] - 'A'];
    if (!q) {
      return 0;
    }
    p = q;
  }
  return cnt[p];
}

void normalize(string& s) {
  for (int i = 0; i < s.size(); ++i) {
    for (int x = 0; x < 4; ++x) {
      if (s[i] == alpha[x]) {
        s[i] = ('A' + x);
        break;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
    normalize(s[i]);
  }

  sort(s.begin(), s.end());

  vector<vector<pair<int, int>>> at(n + 1);
  vector<string> q(m);
  for (int i = 0; i < m; ++i) {
    string p;
    cin >> p >> q[i];
    normalize(p);
    normalize(q[i]);
    reverse(q[i].begin(), q[i].end());
    int l = lower_bound(s.begin(), s.end(), p) - s.begin();
    int r = lower_bound(s.begin(), s.end(), next(p)) - s.begin();
    at[l].emplace_back(i, -1);
    at[r].emplace_back(i, +1);
  }

  vector<int> ans(m);
  for (int i = 0; i < n; ++i) {
    insert(string(s[i].rbegin(), s[i].rend()));
    for (auto& [x, d] : at[i + 1]) {
      ans[x] += d * count(q[x]);
    }
  }

  for (int i = 0; i < m; ++i) {
    cout << ans[i] << "\n";
  }

  return 0;
}

Compilation message

selling_rna.cpp: In function 'void insert(const string&)':
selling_rna.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'int count(const string&)':
selling_rna.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'void normalize(std::string&)':
selling_rna.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 17492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10592 KB Output is correct
2 Incorrect 21 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -