Submission #1359700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359700		waygonz	Mutating DNA (IOI21_dna)	C++20	100 / 100	20 ms	9724 KiB

dna

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

using namespace std;

const int N = (int)1e5 + 1;

int p[4][4][N+1], cnt[3][4][N+1];

int val(char c) {
	if (c == 'A') return 1;
	if (c == 'C') return 2;
	if (c == 'T') return 3;
}

void init(std::string a, std::string b) {
	int n = a.length();
	for (int i = 1; i <= n; i++) {
		char s = val(a[i-1]), t = val(b[i-1]);
		for (int j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				if (j <= 3) cnt[j][k][i] = cnt[j][k][i-1];
				p[j][k][i] = p[j][k][i-1];
			}
		}
		cnt[1][s][i]++;
		cnt[2][t][i]++;
		p[s][t][i]++;
	}
}

int get_distance(int x, int y) {
	x++, y++;
	for (int i = 1; i <= 3; i++)
		if (cnt[1][i][y] - cnt[1][i][x-1] != cnt[2][i][y] - cnt[2][i][x-1])
			return -1;
	int ans = 0;
	int ac = p[1][2][y] - p[1][2][x-1];
	int ca = p[2][1][y] - p[2][1][x-1];
	ans += min(ac, ca);
	int ct = p[2][3][y] - p[2][3][x-1];
	int tc = p[3][2][y] - p[3][2][x-1];
	ans += min(ct, tc);
	int ta = p[3][1][y] - p[3][1][x-1];
	int at = p[1][3][y] - p[1][3][x-1];
	ans += min(ta, at);
	ans += 2 * (max(ta, at) - min(ta, at));
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int val(char)':
dna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16