답안 #467656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467656	2021-08-24T00:14:56 Z	iggaboi	DNA 돌연변이 (IOI21_dna)	C++17	56 / 100	40 ms	6528 KB

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

using namespace std;

vector <int> noteq;
vector <array <int, 3>> cnta, cntb;

void init(std::string a, std::string b) {
	int n = a.size();
	cnta.assign(n, {0, 0, 0});
	cntb.assign(n, {0, 0, 0});
	noteq.assign(n, 0);
	int mpa = 0, mpt = 1, mpc = 2;
      noteq[0] = a[0] != b[0];

      cnta[0][mpa] = a[0] == 'A';
      cnta[0][mpt] = a[0] == 'T';
      cnta[0][mpc] = a[0] == 'C';

      cntb[0][mpa] = b[0] == 'A';
      cntb[0][mpt] = b[0] == 'T';
      cntb[0][mpc] = b[0] == 'C';
      for (int i = 1; i < n; ++i) {
            noteq[i] = noteq[i - 1] + (a[i] != b[i]);

            cnta[i][mpa] = cnta[i - 1][mpa];
            cnta[i][mpt] = cnta[i - 1][mpt];
            cnta[i][mpc] = cnta[i - 1][mpc];

            cntb[i][mpa] = cntb[i - 1][mpa];
            cntb[i][mpt] = cntb[i - 1][mpt];
            cntb[i][mpc] = cntb[i - 1][mpc];

            cnta[i][mpa] += a[i] == 'A';
            cnta[i][mpt] += a[i] == 'T';
            cnta[i][mpc] += a[i] == 'C';

            cntb[i][mpa] += b[i] == 'A';
            cntb[i][mpt] += b[i] == 'T';
            cntb[i][mpc] += b[i] == 'C';
      }
}

int get(int i, int j, int mp, int t) {
	if (t == 1) return cnta[j][mp] - (i ? cnta[i - 1][mp] : 0);
	return cntb[j][mp] - (i ? cntb[i - 1][mp] : 0);
}

int get_distance(int x, int y) {
	int aa = get(x, y, 0, 1), at = get(x, y, 1, 1), ac = get(x, y, 2, 1);
	int ba = get(x, y, 0, 2), bt = get(x, y, 1, 2), bc = get(x, y, 2, 2);
	int neq = noteq[y] - (x ? noteq[x - 1] : 0);

	if (aa != ba || at != bt || ac != bc) return -1;

	return neq + 1 >> 1;
}

Compilation message

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  return neq + 1 >> 1;
      |         ~~~~^~~

Subtask #1
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	6156 KB	Output is correct
2	Correct	38 ms	6244 KB	Output is correct
3	Correct	37 ms	5980 KB	Output is correct
4	Correct	40 ms	6272 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	5 ms	3788 KB	Output is correct
5	Correct	5 ms	3760 KB	Output is correct
6	Correct	4 ms	3760 KB	Output is correct
7	Correct	4 ms	3532 KB	Output is correct
8	Correct	4 ms	3788 KB	Output is correct
9	Correct	5 ms	3788 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	5 ms	3788 KB	Output is correct
5	Correct	5 ms	3760 KB	Output is correct
6	Correct	4 ms	3760 KB	Output is correct
7	Correct	4 ms	3532 KB	Output is correct
8	Correct	4 ms	3788 KB	Output is correct
9	Correct	5 ms	3788 KB	Output is correct
10	Correct	39 ms	6112 KB	Output is correct
11	Correct	38 ms	6252 KB	Output is correct
12	Correct	37 ms	6224 KB	Output is correct
13	Correct	38 ms	6376 KB	Output is correct
14	Correct	39 ms	6504 KB	Output is correct
15	Correct	38 ms	6508 KB	Output is correct
16	Correct	36 ms	6184 KB	Output is correct
17	Correct	36 ms	6364 KB	Output is correct
18	Correct	38 ms	6528 KB	Output is correct
19	Correct	34 ms	6288 KB	Output is correct
20	Correct	36 ms	6384 KB	Output is correct
21	Correct	36 ms	6528 KB	Output is correct

Subtask #4
0.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	5 ms	3788 KB	Output is correct
5	Correct	5 ms	3760 KB	Output is correct
6	Correct	4 ms	3760 KB	Output is correct
7	Correct	4 ms	3532 KB	Output is correct
8	Correct	4 ms	3788 KB	Output is correct
9	Correct	5 ms	3788 KB	Output is correct
10	Correct	4 ms	3532 KB	Output is correct
11	Correct	5 ms	3788 KB	Output is correct
12	Incorrect	4 ms	3532 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	6156 KB	Output is correct
2	Correct	38 ms	6244 KB	Output is correct
3	Correct	37 ms	5980 KB	Output is correct
4	Correct	40 ms	6272 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	5 ms	3788 KB	Output is correct
12	Correct	5 ms	3760 KB	Output is correct
13	Correct	4 ms	3760 KB	Output is correct
14	Correct	4 ms	3532 KB	Output is correct
15	Correct	4 ms	3788 KB	Output is correct
16	Correct	5 ms	3788 KB	Output is correct
17	Correct	39 ms	6112 KB	Output is correct
18	Correct	38 ms	6252 KB	Output is correct
19	Correct	37 ms	6224 KB	Output is correct
20	Correct	38 ms	6376 KB	Output is correct
21	Correct	39 ms	6504 KB	Output is correct
22	Correct	38 ms	6508 KB	Output is correct
23	Correct	36 ms	6184 KB	Output is correct
24	Correct	36 ms	6364 KB	Output is correct
25	Correct	38 ms	6528 KB	Output is correct
26	Correct	34 ms	6288 KB	Output is correct
27	Correct	36 ms	6384 KB	Output is correct
28	Correct	36 ms	6528 KB	Output is correct
29	Correct	4 ms	3532 KB	Output is correct
30	Correct	5 ms	3788 KB	Output is correct
31	Incorrect	4 ms	3532 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #467656

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 22.0 / 22.0

Subtask #3 13.0 / 13.0

Subtask #4 0.0 / 28.0

Subtask #5 0.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
22.0 / 22.0

Subtask #3
13.0 / 13.0

Subtask #4
0.0 / 28.0

Subtask #5
0.0 / 16.0