oj.uz

Submission #342853

# Submission time Handle Problem Language Result Execution time Memory
342853 2021-01-03T04:34:17 Z KoD Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 240228 KB 
#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 15 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

template <class T>
using Vec = std::vector<T>;

constexpr usize match(const char c) {
  if (c == 'A') return 0;
  if (c == 'G') return 1;
  if (c == 'C') return 2;
  if (c == 'U') return 3;
  return 4;
}

struct Node {
  std::array<usize, 4> next{};
  Vec<usize> idx;
};

usize next(Vec<Node> &trie, const usize u, const usize k) {
  if (trie[u].next[k] == 0) {
    const auto n = trie.size();
    trie.push_back(Node {});
    trie[u].next[k] = n;
  }
  return trie[u].next[k];
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  usize N, M;
  std::cin >> N >> M;
  Vec<Node> front, back;
  front.push_back(Node {});
  back.push_back(Node {});
  for (auto i: range(0, N)) {
    std::string S;
    std::cin >> S;
    usize pf = 0, pb = 0;
    for (auto j: range(0, S.size())) {
      pf = next(front, pf, match(S[j]));
      pb = next(back, pb, match(S[S.size() - j - 1]));
      front[pf].idx.push_back(i);
      back[pb].idx.push_back(i);
    }
  }
  while (M--) {
    std::string P, Q;
    std::cin >> P >> Q;
    usize pf = 0, pb = 0;
    for (auto i: range(0, P.size())) {
      pf = next(front, pf, match(P[i]));
    }
    for (auto i: range(0, Q.size())) {
      pb = next(back, pb, match(Q[Q.size() - i - 1]));
    }
    Vec<usize> state(N);
    for (auto i: front[pf].idx) {
      state[i] |= 1;
    }
    for (auto i: back[pb].idx) {
      state[i] |= 2;
    }
    std::cout << std::count(state.begin(), state.end(), 3) << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 194288 KB Output is correct
2 Correct 490 ms 185036 KB Output is correct
3 Correct 445 ms 192396 KB Output is correct
4 Correct 460 ms 183696 KB Output is correct
5 Correct 503 ms 240228 KB Output is correct
6 Correct 477 ms 240176 KB Output is correct
7 Correct 168 ms 37228 KB Output is correct
8 Correct 416 ms 154280 KB Output is correct
9 Correct 390 ms 141808 KB Output is correct
10 Correct 485 ms 145208 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 437 ms 194288 KB Output is correct
9 Correct 490 ms 185036 KB Output is correct
10 Correct 445 ms 192396 KB Output is correct
11 Correct 460 ms 183696 KB Output is correct
12 Correct 503 ms 240228 KB Output is correct
13 Correct 477 ms 240176 KB Output is correct
14 Correct 168 ms 37228 KB Output is correct
15 Correct 416 ms 154280 KB Output is correct
16 Correct 390 ms 141808 KB Output is correct
17 Correct 485 ms 145208 KB Output is correct
18 Execution timed out 1558 ms 2736 KB Time limit exceeded
19 Halted 0 ms 0 KB -