제출 #1074703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074703		nima_aryan	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	182 ms	254032 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

vector<char> alpha{'A', 'G', 'C', '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 = 1.2E7;
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][find(alpha.begin(), alpha.end(), s[i]) - alpha.begin()];
    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][find(alpha.begin(), alpha.end(), s[i]) - alpha.begin()];
    if (!q) {
      return 0;
    }
    p = q;
  }
  return cnt[p];
}

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

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

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

  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> 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];
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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) {
      |                   ~~^~~~~~~~~~

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