Submission #1198124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198124		HappyCapybara	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	8008 KiB

dna

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

vector<vector<int>> ps;

void init(string a, string b){
	int n = a.size();
	ps.resize(n+1, vector<int>(6, 0));
	for (int i=0; i<n; i++){
		ps[i+1][0] = ps[i][0]+(a[i] == 'A' && b[i] == 'T');
		ps[i+1][1] = ps[i][1]+(a[i] == 'T' && b[i] == 'A');
		ps[i+1][2] = ps[i][2]+(a[i] == 'A' && b[i] == 'C');
		ps[i+1][3] = ps[i][3]+(a[i] == 'C' && b[i] == 'A');
		ps[i+1][4] = ps[i][4]+(a[i] == 'T' && b[i] == 'C');
		ps[i+1][5] = ps[i][5]+(a[i] == 'C' && b[i] == 'T');
	}
}

int get_distance(int x, int y){
	vector<int> v(6);
	for (int i=0; i<6; i++) v[i] = ps[y+1][i]-ps[x][i];
	int a = min(v[0], v[1])+min(v[2], v[3])+min(v[4], v[5]);
	if (v[0]+v[2] != v[1]+v[3] || v[1]+v[4] != v[0]+v[5] || v[3]+v[5] != v[2]+v[4]) return -1;
	return a+(v[0]+v[1]+v[2]+v[3]+v[4]+v[5]-2*a)/3*2;
}

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