Submission #1181438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181438		peteza	Mutating DNA (IOI21_dna)	C++20	0 / 100	21 ms	5632 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int qs[100005][3][3];
int vals[3][3];

int conv(char x) {
	if(x == 'A') return 0;
	if(x == 'T') return 1;
	return 2;
}

void init(std::string a, std::string b) {
	n = a.size();
	for(int i=1;i<=n;i++) {
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				qs[i][j][k] = qs[i-1][j][k];
			}
		}
		qs[i][conv(a[i-1])][conv(b[i-1])]++;
	}
}

int get_distance(int x, int y) {
	y++;
	for(int j=0;j<3;j++) {
		for(int k=0;k<3;k++) vals[j][k] = qs[y][j][k] - qs[x][j][k];
	}
	int v01, v02, v12;
	v01 = min(vals[0][1], vals[1][0]);
	v02 = min(vals[0][2], vals[2][0]);
	v12 = min(vals[1][2], vals[2][1]);
	int ans = v01 + v02 + v12;
	vals[0][1] -= v01; vals[1][0] -= v01;
	vals[0][2] -= v02; vals[2][0] -= v02;
	vals[1][2] -= v12; vals[2][1] -= v12;
	if(vals[0][1] == vals[1][2] && vals[1][2] == vals[2][0]) {
		ans += llabs(vals[0][1]) * 2;
	} else return -1;
	return ans;
}

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