Submission #1249318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249318		Nurislam	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	7180 KiB

dna

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

using namespace std;

vector<array<int,3>> pa, pb;
vector<array<int,6>> p;
map<char,int> mp;

void init(string a, string b) {
	int n = a.size();
	pa.resize(n+1);
	pb.resize(n+1);
	p.resize(n+1);
	
	mp['A'] = 0;
	mp['T'] = 1;
	mp['C'] = 2;
	for(int i = 1; i <= n; i ++ ) {
		for(int j = 0; j < 3; j ++ ) pa[i][j] = pa[i-1][j];
		pa[i][mp[a[i-1]]]++;
		for(int j = 0; j < 3; j ++ ) pb[i][j] = pb[i-1][j];
		pb[i][mp[b[i-1]]]++;
		for(int j = 0; j < 6; j ++ ) p[i][j] = p[i-1][j];
		
		// A -> T
		if(a[i-1] == 'A' && b[i-1] == 'T')p[i][0] ++;
		// A -> C
		if(a[i-1] == 'A' && b[i-1] == 'C')p[i][1] ++;
		// C -> A
		if(a[i-1] == 'C' && b[i-1] == 'A')p[i][2] ++;
		// C -> T
		if(a[i-1] == 'C' && b[i-1] == 'T')p[i][3] ++;
		// T -> A
		if(a[i-1] == 'T' && b[i-1] == 'A')p[i][4] ++;
		// T -> C
		if(a[i-1] == 'T' && b[i-1] == 'C')p[i][5] ++;
	};
	
}

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

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