시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 2048 MB | 99 | 60 | 57 | 60.638% |
Grace is a biologist working in a bioinformatics firm in Singapore. As part of her job, she analyses the DNA sequences of various organisms. A DNA sequence is defined as a string consisting of characters "A
", "T
", and "C
". Note that in this task DNA sequences do not contain character "G
".
We define a mutation to be an operation on a DNA sequence where two elements of the sequence are swapped. For example a single mutation can transform "ACTA
" into "AATC
" by swapping the highlighted characters "A
" and "C
".
The mutation distance between two sequences is the minimum number of mutations required to transform one sequence into the other, or $-1$ if it is not possible to transform one sequence into the other by using mutations.
Grace is analysing two DNA sequences $a$ and $b$, both consisting of $n$ elements with indices from $0$ to $n - 1$. Your task is to help Grace answer $q$ questions of the form: what is the mutation distance between the substring $a[x..y]$ and the substring $b[x..y]$? Here, a substring $s[x..y]$ of a DNA sequence $s$ is defined to be a sequence of consecutive characters of s, whose indices are $x$ to $y$ inclusive. In other words, $s[x..y]$ is the sequence $s[x]s[x + 1] \dots s[y]$.
You should implement the following procedures:
void init(string a, string b)
get_distance
.int get_distance(int x, int y)
Consider the following call:
init("ATACAT", "ACTATA")
Let's say the grader calls get_distance(1, 3)
. This call should return the mutation distance between $a[1..3]$ and $b[1..3]$, that is, the sequences "TAC
" and "CTA
". "TAC
" can be transformed into "CTA
" via $2$ mutations: TAC
→ CAT
, followed by CAT
→ CTA
, and the transformation is impossible with fewer than $2$ mutations.
Therefore, this call should return $2$.
Let's say the grader calls get_distance(4, 5)
. This call should return the mutation distance between sequences "AT
" and "TA
". "AT
" can be transformed into "TA
" through a single mutation, and clearly at least one mutation is required.
Therefore, this call should return $1$.
Finally, let's say the grader calls get_distance(3, 5)
. Since there is no way for the sequence "CAT
" to be transformed into "ATA
" via any sequence of mutations, this call should return $-1$.
A
", "T
", and "C
".번호 | 배점 | 제한 |
---|---|---|
1 | 21 | $y - x \le 2$ |
2 | 22 | $q \le 500$, $y - x \le 1000$, each character of $a$ and $b$ is either " |
3 | 13 | Each character of $a$ and $b$ is either " |
4 | 28 | $q \le 500$, $y - x \le 1000$ |
5 | 16 | No additional constraints. |
The sample grader reads the input in the following format:
get_distance
.The sample grader prints your answers in the following format:
get_distance
.C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)