Submission #958345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
958345	2024-04-05T13:15:15 Z	AC2K	Mutating DNA (IOI21_dna)	C++17	56 / 100	28 ms	10788 KB

dna

#include "dna.h"
#include <bits/stdc++.h>

#include <vector>
using namespace std;

int sum[300000];
int suma[3][300000], sumb[3][300000];
const string dna = "ATC";

void init(std::string a, std::string b) {
    memset(sum, 0, sizeof(sum));
    memset(suma, 0, sizeof(suma));
    memset(suma, 0, sizeof(sumb));

    for (int i = 0; i < (int)a.size(); ++i) {
        sum[i + 1] = sum[i] + (a[i] != b[i]);
    }

    for (int j = 0; j < 3; ++j) {
        for (int i = 0; i < (int)a.size(); ++i) {
            suma[j][i + 1] = suma[j][i] + (a[i] == dna[j]);
            sumb[j][i + 1] = sumb[j][i] + (b[i] == dna[j]);
        }
    }
}

int get_distance(int x, int y) {
    ++y;
    for (int i = 0; i < 3; ++i) {
        if (suma[i][y] - suma[i][x] != sumb[i][y] - sumb[i][x]) {
            return -1;
        }
    }
    return (sum[y] - sum[x] + 1) / 2;
}

Subtask #1

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	10512 KB	Output is correct
2	Correct	23 ms	10412 KB	Output is correct
3	Correct	23 ms	10392 KB	Output is correct
4	Correct	23 ms	10764 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	1 ms	6236 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6388 KB	Output is correct
2	Correct	1 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	3 ms	9052 KB	Output is correct
5	Correct	3 ms	9048 KB	Output is correct
6	Correct	3 ms	9052 KB	Output is correct
7	Correct	3 ms	9052 KB	Output is correct
8	Correct	3 ms	9048 KB	Output is correct
9	Correct	3 ms	9048 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6388 KB	Output is correct
2	Correct	1 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	3 ms	9052 KB	Output is correct
5	Correct	3 ms	9048 KB	Output is correct
6	Correct	3 ms	9052 KB	Output is correct
7	Correct	3 ms	9052 KB	Output is correct
8	Correct	3 ms	9048 KB	Output is correct
9	Correct	3 ms	9048 KB	Output is correct
10	Correct	23 ms	10520 KB	Output is correct
11	Correct	24 ms	10420 KB	Output is correct
12	Correct	25 ms	10748 KB	Output is correct
13	Correct	26 ms	10780 KB	Output is correct
14	Correct	28 ms	10764 KB	Output is correct
15	Correct	24 ms	10768 KB	Output is correct
16	Correct	24 ms	10760 KB	Output is correct
17	Correct	24 ms	10788 KB	Output is correct
18	Correct	25 ms	10776 KB	Output is correct
19	Correct	28 ms	10780 KB	Output is correct
20	Correct	24 ms	10764 KB	Output is correct
21	Correct	24 ms	10776 KB	Output is correct

Subtask #4

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6388 KB	Output is correct
2	Correct	1 ms	6236 KB	Output is correct
3	Correct	2 ms	6236 KB	Output is correct
4	Correct	3 ms	9052 KB	Output is correct
5	Correct	3 ms	9048 KB	Output is correct
6	Correct	3 ms	9052 KB	Output is correct
7	Correct	3 ms	9052 KB	Output is correct
8	Correct	3 ms	9048 KB	Output is correct
9	Correct	3 ms	9048 KB	Output is correct
10	Correct	3 ms	9048 KB	Output is correct
11	Correct	3 ms	9052 KB	Output is correct
12	Incorrect	3 ms	9052 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	10512 KB	Output is correct
2	Correct	23 ms	10412 KB	Output is correct
3	Correct	23 ms	10392 KB	Output is correct
4	Correct	23 ms	10764 KB	Output is correct
5	Correct	2 ms	6236 KB	Output is correct
6	Correct	2 ms	6236 KB	Output is correct
7	Correct	1 ms	6236 KB	Output is correct
8	Correct	2 ms	6388 KB	Output is correct
9	Correct	1 ms	6236 KB	Output is correct
10	Correct	2 ms	6236 KB	Output is correct
11	Correct	3 ms	9052 KB	Output is correct
12	Correct	3 ms	9048 KB	Output is correct
13	Correct	3 ms	9052 KB	Output is correct
14	Correct	3 ms	9052 KB	Output is correct
15	Correct	3 ms	9048 KB	Output is correct
16	Correct	3 ms	9048 KB	Output is correct
17	Correct	23 ms	10520 KB	Output is correct
18	Correct	24 ms	10420 KB	Output is correct
19	Correct	25 ms	10748 KB	Output is correct
20	Correct	26 ms	10780 KB	Output is correct
21	Correct	28 ms	10764 KB	Output is correct
22	Correct	24 ms	10768 KB	Output is correct
23	Correct	24 ms	10760 KB	Output is correct
24	Correct	24 ms	10788 KB	Output is correct
25	Correct	25 ms	10776 KB	Output is correct
26	Correct	28 ms	10780 KB	Output is correct
27	Correct	24 ms	10764 KB	Output is correct
28	Correct	24 ms	10776 KB	Output is correct
29	Correct	3 ms	9048 KB	Output is correct
30	Correct	3 ms	9052 KB	Output is correct
31	Incorrect	3 ms	9052 KB	Output isn't correct
32	Halted	0 ms	0 KB	-