Submission #467656

#	Time	Username	Problem	Language	Result	Execution time	Memory
467656		iggaboi	Mutating DNA (IOI21_dna)	C++17	56 / 100	40 ms	6528 KiB

dna

#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 (stderr)

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 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16